P5227摄像头3 | ||
|
问题描述
NK中学里有一条长度为L的笔直道路,同学们可以把该路看作数轴,路的一段坐标为0,一段坐标为L,表示区间[0,L]
在这条路上安装有n个摄像头,每个摄像头都有一定的拍摄区间,第i个摄像头覆盖的区间为$(A_i,B_i)$
何老板想开启其中k个摄像头,使得这k个摄像头的拍摄区间两两没有交集,问k值最大是多少?
输入格式
第一行为一个正整数 \(n\);
在接下来的 \(n\) 行中,每行有 $2$ 个数 \(a_i, b_i\),描述每条线段。
输出格式
输出一个整数,为 \(k\) 的最大值。
样例输入 1
10
7 8
1 7
0 3
4 9
0 6
5 7
0 3
7 8
7 10
4 7
样例输出 1
3
样例输入 2
10
0 3
1 4
15 19
1 2
1 3
2 5
4 7
2 4
3 8
7 12
样例输出 2
5
提示
对于 $20%$ 的数据,\(n \leq 10\);
对于 $50%$ 的数据,\(n \leq 10^3\);
对于 $70%$ 的数据,\(n \leq 10^5\);
对于 $100%$ 的数据,\(n \leq 10^6,\) $0 \leq a_i \lt b_i \leq 10^6$。