Maximum Non-overlapping Lectures

This problem asks you to determine the maximum number of lectures that can be scheduled such that none of them overlap. Each lecture is represented by its starting time and ending time. Two lectures do not overlap if the starting time of one lecture is greater than or equal to the ending time of the previous lecture.

Consider the condition mathematically: for two lectures with intervals \([s_i, e_i]\) and \([s_j, e_j]\), they are non-overlapping if \(s_j \ge e_i\). Using a greedy strategy (sorting by the ending times) guarantees an optimal solution.

inputFormat

The input is read from standard input and consists of a single line containing several space-separated integers. The first integer is \(N\), the number of lectures. It is followed by \(2N\) integers where each consecutive pair represents the start and end times of a lecture.

outputFormat

Output a single integer to standard output, denoting the maximum number of non-overlapping lectures that can be scheduled.

5 1 3 2 4 3 5 6 8 5 7

3