Home => ProblemSet => 2.10-32:区间选点
Problem1597--2.10-32:区间选点

1597: 2.10-32:区间选点

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。

Input

第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

Output

输出一个整数,表示所需的点的最小数量。

Sample Input Copy

3
-1 1
2 4
3 5

Sample Output Copy

2

HINT





1≤N≤105,
−109≤ai≤bi≤109

Source/Category