Maximum Number of Non-overlapping Meetings

This problem is a classic interval scheduling challenge where you are given the start and end times of several meetings. Your task is to choose the maximum number of meetings that can be scheduled in one day without any overlaps.

To solve this, you should sort the meetings by their finishing times and then use a greedy algorithm to select meetings. In other words, if you have meetings given by intervals \( (s_i, e_i) \), then you must choose a maximal subset such that for any two consecutive meetings, \( s_{i+1} \ge e_i \).

inputFormat

The first line contains a single integer n, the number of meetings. Each of the following n lines contains two space-separated integers representing the start and end times of a meeting.

outputFormat

Output a single integer denoting the maximum number of non-overlapping meetings that can be scheduled.## sample

3
1 2
2 3
3 4

3