P1803 凌乱的yyy / 线段覆盖
题目描述
快 noip 了,yyy 很紧张!
现在各大 oj 上有 n 个比赛,每个比赛的开始、结束的时间点是知道的。
yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。
所以,他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 2 个及以上的比赛。
输入格式
第一行输入一个整数 n(1≦n≦106) 代表比赛的数量。
此后 n 行,第 i 行输入两个整数 ai,bi(0≦ai<bi≦106) 代表第 i 场比赛的开始时间和结束时间。
输出格式
在一行上输出一个整数,代表最多能参加的比赛数目。
测试样例
3
0 2
2 4
1 3
2
样例 1 解释
可以选择第 1 场比赛(时间区间 [0,2])和第 2 场比赛(时间区间 [2,4]),两场比赛在时刻 2 处首尾相接,并不冲突,因此最多参加 2 场。
数据范围与提示
对于 20% 的数据,n≦10。
对于 50% 的数据,n≦103。
对于 70% 的数据,n≦105。
对于 100% 的数据,1≦n≦106,0≦ai<bi≦106。