#P18278. The Best Wife
The Best Wife
The Best Wife
Sofia 想参加一些活动。第 个活动在第 天开始、第 天结束;如果选择参加,就必须在闭区间 的每一天都参加。
她每天至多参加一个活动。因此,即使一个活动的结束日期恰好等于另一个活动的开始日期,这两个活动也不能同时选择。
活动按顺序逐个出现。对每个 ,请输出只考虑前 个活动时,最多能参加多少个活动。每个前缀可以重新选择最优方案;此前输出不会限制后来的选择。
输入格式
第一行包含一个整数 ,表示活动数。
接下来 行,每行包含两个整数 ,表示第 个活动的开始、结束日期。
输出格式
输出 行。第 行包含一个整数,表示前 个活动中最多能参加的活动数。
数据范围
- ;
- 。
活动可以具有相同的开始、结束日期,也可以完全重复。输入只有一组数据。
样例
5
1 3
3 5
1 2
5 6
4 4
1
1
2
2
3
前两个活动在第 天冲突。前三个活动中,可以选择 和 。全部五个活动中,可以选择 、、。