问题 3237 --线段(segment.cpp)

3237: 线段(segment.cpp)

时间限制: 1 Sec  内存限制: 256 MB
提交: 3  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

在银河系边缘的「碎星带」,星际矿工们发现了一种稀有晶体矿脉。这些矿脉在数轴上可以用一条线段表示,且这条线段的左右端点分别是li,ri,但附近的太空浮雷群会周期性引爆,摧毁矿脉。 联盟工程师设计了一种「能量锚点」——在某个坐标激活锚点后,可以保护以其为中心、半径为零的整条矿脉(即覆盖该点所在的任何矿脉区间)。但锚点需要消耗大量反物质能源,每多部署一个,都会让 舰队的曲速引擎续航减少 。 矿工长紧急求助:“我们需要用最少的锚点护住所有矿脉!否则舰队无法返航!”作为随舰AI,请计算最小锚点数量。 

输入

输入一共有n+1行。

第一行一个整数n,表示有n个矿脉。 

接下来的n行每行有两个整数li,ri,表示第i个矿脉的左右端点。

输出

输出一行一个整数 , 表示最小锚点数量。 

样例输入

输入样例1
2
0 2
2 5
输入样例2
5
0 3
2 4
4 8
8 10
7 7

样例输出

输出样例1
1
输出样例2
3

提示


样例解释 



样例一中,在2点设置一个锚点,就可以覆盖所有的矿脉,所以答案为 。 



样例二中,分别在3,7,8这三个点设置锚点,就可以覆盖所有的矿脉,当然,还有其他的覆盖方案,比如(3,7,10),所以最小设置三个锚点就可以覆盖所有的矿脉。 



数据范围 



 对于20%的数据,n<=100,1<=li<=ri<=100 ;



 对于100%的数据,n<=10^5. 1<=li<=ri<=10^9

来源

[提交][状态]