278. Fit the Most Meetings
Challenge1000 ms256 MBSolved by 0%
n meetings each have a start and an end. One room. A meeting may start at
the exact moment another ends.
Print the largest number of meetings that can be held.
Sorting by START time and taking greedily is wrong: one long meeting at the front blocks several short ones.
Sort by END time instead. Always take the meeting that finishes earliest among those that can still fit, because finishing early leaves the most room for everything after it. That exchange argument is what makes the greedy choice provably optimal here.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ start ≤ end ≤ 1000000000`
Input
The first line contains an integer n.
Each of the next n lines contains two integers start and end.
Output
Print one integer, the maximum number of meetings that fit.
Input6
1 2
3 4
0 6
5 7
8 9
5 9
Output4
Notehas a long meeting that a start-time greedy would wrongly take first
Input1
1 2
Output1
Noteis a single meeting
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution