Maximum Non-Overlapping Intervals

Given a set of intervals, each defined by a starting point (s_i) and an ending point (e_i), determine the maximum number of intervals that can be selected such that no two intervals overlap. Two intervals ([s_i, e_i]) and ([s_j, e_j]) are considered non-overlapping if (s_j \ge e_i) (assuming intervals are processed in order of increasing end times). This problem can be solved using a greedy algorithm: sort the intervals by their ending times and select intervals sequentially, always picking the next interval that starts after the current one ends.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (n) denoting the number of intervals. Each of the following (n) lines contains two space-separated integers (s_i) and (e_i), representing the start and end of the (i)-th interval.

outputFormat

Output a single integer to standard output (stdout) that represents the maximum number of non-overlapping intervals.## sample

1
1 2

1