Maximum Non-overlapping Meetings

You are given N meetings with their start and end times. Your task is to select the maximum number of meetings that can be scheduled such that no two meetings overlap.

Formally, if the i^th meeting is represented by the interval \([s_i, e_i]\), you need to find the maximum number of intervals you can choose such that for any two chosen intervals \([s_i, e_i]\) and \([s_j, e_j]\) with \(i \neq j\), the condition \(s_j > e_i\) (or vice versa) is satisfied.

This is a classic greedy algorithm problem: by sorting the meetings by their ending times, you can always pick the meeting that finishes first, and then select the next meeting that starts strictly after the current meeting's end time.

inputFormat

The first line contains an integer N representing the number of meetings. The following N lines each contain two integers s and e representing the start and end times of a meeting respectively.

Note: Meetings are considered non-overlapping if the start time of a meeting is strictly greater than the end time of the previously selected meeting.

outputFormat

Output a single integer which is the maximum number of non-overlapping meetings that can be scheduled.

3
1 4
2 5
3 6

1