Maximum Non-Overlapping Events

You are given a list of events, each defined by a start time and an end time. Your task is to determine the maximum number of events you can attend without any overlaps.

Two events are non-overlapping if the start time of one event is greater than or equal to the end time of the other event. In other words, if you attend an event ending at time \(e\), you can only attend another event that starts at or after time \(e\).

This problem can be efficiently solved using a greedy algorithm by sorting the events by their ending times.

inputFormat

The input is read from standard input and has the following format:

• The first line contains a single integer \(n\) (\(0 \leq n \leq 10^5\)), representing the number of events.
• Each of the following \(n\) lines contains two space-separated integers \(s\) and \(e\) (with \(1 \leq s < e \leq 10^9\)), representing the start time and end time of an event.

outputFormat

Output a single integer on standard output: the maximum number of non-overlapping events that can be attended.

4
1 4
2 3
3 4
5 6

3