Maximum Non-overlapping Events

You are given a list of events. Each event is described by its start time and end time. Your task is to determine the maximum number of events that can be attended without any overlap. An event can be attended if its start time is not earlier than the ending time of the previously attended event. A greedy algorithm that always chooses the event with the earliest finish time guarantees an optimal solution.

Formally, each event is represented as \( (s_i, e_i) \), where \( s_i \) is the start time and \( e_i \) is the end time. The goal is to select a maximum subset of events such that \( s_{i+1} \ge e_i \) for every consecutive pair in the chosen subset.

inputFormat

The input begins with a single integer \( n \) \((1 \le n \le 10^5)\), representing the number of events. Each of the next \( n \) lines contains two space-separated integers \( s \) and \( e \) \((1 \le s < e \le 10^9)\) that denote the start and end times of an event.

outputFormat

Output a single integer—the maximum number of events that can be attended without overlapping.

3
1 2
2 3
3 4

3