Maximum Non-Overlapping Events

You are given a set of events, where each event is represented by its start and end times as an interval \((s_i, e_i)\). Your task is to determine the maximum number of events you can attend without any overlaps. Two events \((s_i, e_i)\) and \((s_j, e_j)\) are considered non-overlapping if \(s_j \gt e_i\) (i.e. the start time of the latter event is strictly greater than the end time of the former).

The optimal solution is based on a greedy algorithm: first, sort the events by their end times and then select events sequentially, ensuring that each chosen event starts after the last selected event ended.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) representing the number of events. Each of the following \(n\) lines contains two space-separated integers \(s\) and \(e\), denoting the start and end times of an event, respectively.

outputFormat

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

0

0