Maximum Non-overlapping Events

You are given a list of events, where each event is represented by its start and end times. Your task is to determine the maximum number of events that can be attended if you can only attend non-overlapping events.

An event is represented by a pair of integers \( (s,e) \) where \( s \) is the start time and \( e \) is the end time. Two events \( (s_1,e_1) \) and \( (s_2,e_2) \) are non-overlapping if \( s_2 \geq e_1 \) when sorted by end times.

Use a greedy strategy to maximize the number of events you can attend.

inputFormat

The first line of input contains a single integer \( N \) — the number of events. Each of the following \( N \) lines contains two space-separated integers \( start \) and \( end \) representing the start time and end time of an event, respectively.

outputFormat

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

5
1 3
2 4
3 5
6 8
7 9

3