Home => ProblemSet => 2.10-34:区间分组
Problem1600--2.10-34:区间分组

1600: 2.10-34:区间分组

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