Maximum Non-Overlapping Events

You are given a list of events, each with a start time and an end time. Your task is to determine the maximum number of events you can attend without any overlap. Two events do not overlap if the start time of an event is not less than the end time of the previously attended event.

This problem can be solved optimally using a greedy algorithm. First, sort the events by their end times. Then, iteratively select events that start after or at the end time of the last selected event. The process can be formally described by the condition: $$s_i \geq e_{last},$$ where $$s_i$$ is the start time of the current event and $$e_{last}$$ is the end time of the most recently selected event.

inputFormat

The input is read from standard input (stdin). The first line contains an integer n denoting the number of events. Each of the following n lines contains two integers representing the start time and end time of an event.

outputFormat

Output a single integer to standard output (stdout), which denotes the maximum number of non-overlapping events that can be attended.

3
1 3
2 5
4 6

2