Non-Overlapping Intervals Selection

You are given a list of events represented by intervals on the number line. Each event is represented by two integers, the start time and the end time. Your task is to select the maximum number of non-overlapping intervals from the list. Formally, given a set of intervals ( (s_i, e_i) ) for ( i = 1, 2, \dots, n ), you need to find a subset of intervals ( I ) (with maximum size) such that for every two intervals ( (s_i, e_i) ) and ( (s_j, e_j) ) in ( I ) with ( i \neq j ), the intervals do not overlap, i.e. ( s_j \ge e_i ) or ( s_i \ge e_j ).

The input is given via standard input in the following format. The first line contains an integer ( n ), denoting the number of intervals. Each of the following ( n ) lines contains two space-separated integers representing the start time and the end time of an interval.

The output should be a single integer printed on standard output, representing the maximum number of non-overlapping intervals that can be selected.

Note: The intervals may not be sorted. Use a greedy approach by sorting the intervals by their end times (and start times as a tiebreaker) to achieve an optimal solution.

inputFormat

The first line of input contains an integer ( n ), representing the number of intervals. Each of the following ( n ) lines contains two integers ( s_i ) and ( e_i ), representing the starting and ending points of the ( i^{th} ) interval.

outputFormat

Output a single integer, which is the maximum number of non-overlapping intervals that can be selected.## sample

5
1 3
2 5
4 7
6 8
8 10

3