Maximum Meetings Scheduling

You are given a collection of meetings, each represented by a start time and an end time, denoted as \( (s_i, e_i) \). Your task is to schedule as many meetings as possible without any overlaps. Two meetings \( (s_i, e_i) \) and \( (s_j, e_j) \) are said to be non-overlapping if \( s_j \geq e_i \) when arranged in increasing order of their end times.

The strategy to solve this problem is based on a greedy algorithm, where you sort all meetings by their ending times and then select meetings one by one, ensuring that the start time of the current meeting is not less than the end time of the previously selected meeting.

inputFormat

The first line of input contains an integer \( n \) representing the number of meetings. Each of the following \( n \) lines contains two space-separated integers representing the start time and the end time of a meeting, respectively.

outputFormat

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

3
900 1000
1000 1100
1100 1200

3