Maximum Non-Overlapping Meetings

You are given a series of meetings, each represented by a pair of integers indicating the start and end times. 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 a meeting is greater than or equal to the end time of the last scheduled meeting. This problem can be optimally solved using a greedy algorithm by sorting the meetings by their finish times.

Formally, if we denote a meeting by \((s, e)\) where \(s\) is the start time and \(e\) is the end time, find the maximum number of meetings that can be chosen such that for every consecutive pair \((s_i, e_i)\) and \((s_j, e_j)\) in the chosen set, \(s_j \geq e_i\).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing 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 to standard output (stdout) representing the maximum number of non-overlapping meetings that can be scheduled.## sample

5
1 4
2 5
9 12
5 9
5 5

4