Maximum Non-overlapping Events

You are given a list of events, where each event is described by its start time and end time. Your task is to determine the maximum number of non-overlapping events that can be attended. Two events are considered non-overlapping if the start time of an event is greater than or equal to the end time of the previously selected event.

This problem can be modeled as an interval scheduling maximization problem. A well-known greedy algorithm can be applied: first, sort the events by their end times, and then select events one by one, choosing the next event only if its start time is not less than the finish time of the last selected event.

In mathematical notation, given a set of events \( E = \{(s_i, e_i)\}_{i=1}^N \), find the largest subset \( A \subseteq E \) such that for every pair of consecutive events \((s_j, e_j)\) and \((s_k, e_k)\) in \(A\), we have \( s_k \ge e_j \).

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \(N\), representing the number of events. The next \(N\) lines each contain two integers \(s\) and \(e\), where \(s\) is the start time and \(e\) is the end time of an event.

outputFormat

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

5
1 4
2 3
3 5
6 8
7 9

3