LG#P1803. 线段覆盖

线段覆盖

P1803 凌乱的yyy / 线段覆盖

题目描述

\hspace{15pt}快 noip 了,yyy 很紧张!

\hspace{15pt}现在各大 oj 上有 nn 个比赛,每个比赛的开始、结束的时间点是知道的。

\hspace{15pt}yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。

\hspace{15pt}所以,他想知道他最多能参加几个比赛。

\hspace{15pt}由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 22 个及以上的比赛。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦106)n \left(1 \leqq n \leqq 10^6\right) 代表比赛的数量。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 ai,bi(0≦ai<bi≦106)a_i, b_i \left(0 \leqq a_i < b_i \leqq 10^6\right) 代表第 ii 场比赛的开始时间和结束时间。

输出格式

\hspace{15pt}在一行上输出一个整数,代表最多能参加的比赛数目。

测试样例

3
0 2
2 4
1 3

2

样例 1 解释

\hspace{15pt}可以选择第 11 场比赛(时间区间 [0,2][0, 2])和第 22 场比赛(时间区间 [2,4][2, 4]),两场比赛在时刻 22 处首尾相接,并不冲突,因此最多参加 22 场。

数据范围与提示

\hspace{15pt}对于 20%20\% 的数据,n≦10n \leqq 10。

\hspace{15pt}对于 50%50\% 的数据,n≦103n \leqq 10^3。

\hspace{15pt}对于 70%70\% 的数据,n≦105n \leqq 10^5。

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1061 \leqq n \leqq 10^6,0≦ai<bi≦1060 \leqq a_i < b_i \leqq 10^6。