Maximum Non-Overlapping Events

You are given a set of events, each with a start time and an end time. Your task is to determine the maximum number of events that can be scheduled without any overlapping time slots.

Formally, you are given an integer \(n\) and \(n\) pairs of integers \((s_i, e_i)\), where \(s_i\) is the start time and \(e_i\) is the end time of the \(i^{th}\) event. Two events \((s_i, e_i)\) and \((s_j, e_j)\) are considered non-overlapping if \(s_j \geq e_i\) (assuming that the events are processed in order of increasing end times). Implement an efficient algorithm to compute the maximum number of non-overlapping events.

Hint: A greedy algorithm that sorts events by their end times is optimal.

The key idea is to always select the event that ends the earliest, and then continue selecting the next event starting after the current event's finish time.

inputFormat

The input begins with a single integer \(n\) denoting the number of events. This is followed by \(n\) lines, each containing two integers representing the start and end times of an event.

For example:

4
1 4
2 5
3 8
10 12

outputFormat

Output a single integer representing the maximum number of non-overlapping events that can be scheduled.

4
1 4
2 5
3 8
10 12

2