Maximum Non-Overlapping Meetings

You are given a set of meetings, each with a start time and an end time. Your task is to determine the maximum number of meetings that can be scheduled without any overlaps. Two meetings are considered non-overlapping if the start time of one meeting is greater than or equal to the end time of the previously scheduled meeting.

The problem can be formulated as follows: Given a list of meetings \( (s_i, e_i) \) for \( i = 1,2,\ldots,n \), select the largest subset of meetings such that for any two consecutive meetings \( (s_i, e_i) \) and \( (s_j, e_j) \) in the sequence, the condition \( s_j \geq e_i \) holds. A common strategy is to use a greedy algorithm where meetings are first sorted by their end times.

Hint: Sorting by the end times ensures that you always have the maximum remaining time available for scheduling subsequent meetings.

inputFormat

The input is given via stdin in the following format:

N
s1 e1
s2 e2
... 
sN eN

Where:

• N is the number of meetings.
• si and ei are the start and end times of the i-th meeting.

outputFormat

The output is a single integer written to stdout representing the maximum number of non-overlapping meetings that can be scheduled.

6
1 4
2 3
3 5
7 8
5 6
4 7

4