Competitions
Greedy
Segments
Some segments are given on a line. What is the maximum number of segments can be selected so that no two of them intersects? The segments are considered open.
Input
The first line contains the number of segments n (1 ≤ n ≤ 105
). Next n lines describe the segments: i-th line contains two integers li
and ri
(1 ≤ li
< ri
≤ 109
) - the coordinates of segment's starting and ending point.
Output
Print the maximum number of non intersecting segments.
Input example #1
2 1 2 3 5
Output example #1
2
Input example #2
2 1 3 2 6
Output example #2
1
Input example #3
3 2 4 3 5 1 3
Output example #3
2