Maximum Non-Overlapping Events

You are given a set of events, each with a start time and an end time. Your task is to determine the maximum number of events that can be scheduled without overlapping. Two events are considered non-overlapping if the start time of one is greater than or equal to the end time of the other.

The optimal solution is based on a greedy algorithm. Sort the events by their end times (i.e., sort by $t_{end}$) and then select events one by one, ensuring that each event starts no earlier than the end time of the previously selected event.

inputFormat

The input is given via standard input (stdin). The first line contains an integer N denoting the number of events. Each of the next N lines contains two integers S and E representing the start time and end time of an event, respectively.

outputFormat

Output, via standard output (stdout), a single integer representing the maximum number of non-overlapping events that can be scheduled.

5
0 3
1 2
3 5
4 6
5 8

3