Maximum Non-Overlapping Trains

Given a list of train schedules represented by their start and end times, determine the maximum number of non-overlapping trains that can be scheduled on a single track.

This is a classic interval scheduling optimization problem. The optimal solution can be obtained by applying a greedy algorithm: sort all trains by their ending time and select each train whose starting time is not less than the ending time of the previously selected train.

Mathematically, if the previously selected train ends at \(E\), then the next train can be selected if its start time \(S\) satisfies \(S \geq E\).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (N) denoting the number of trains. Each of the next (N) lines contains two space-separated integers representing the start and end times of a train.

outputFormat

Output a single integer to standard output (stdout), representing the maximum number of non-overlapping trains that can be scheduled on the track.## sample

3
1 3
2 5
4 6

2