Meeting Room Scheduling
InterviewTime limit2sMemory limit128 MB
Given N meetings with start and end times, select the maximum number of non-overlapping meetings using a classic greedy interval scheduling approach.
Problem
There is one meeting room. Given (N) meetings that want to use it, find the maximum number of meetings that can be scheduled so that no two selected meetings overlap.
Each meeting has a start time and an end time. Once a meeting starts, it cannot be interrupted. A meeting may start at the exact time another meeting ends. A meeting may also have the same start and end time; such a meeting is considered to end immediately after it starts.
Input
The first line contains the number of meetings (N). (1 \le N \le 100{,}000)
Each of the next (N) lines contains two integers, the start time and end time of one meeting, separated by a space. Each start time and end time is an integer from (0) to (2^{31}-1), inclusive.
Output
Print the maximum number of meetings that can use the meeting room.
Hint
One possible selection is ((1,4), (5,7), (8,11), (12,14)).