1437. Fewest Removals to Stop Overlaps
Given n intervals, print the fewest that must be removed so that none of
the rest overlap. Intervals touching at a boundary do NOT overlap, so [1,2]
and [2,3] may both stay.
This is the meeting room problem inverted. The fewest removed is n minus the
most that can be kept, and the most that can be kept is found by sorting on END
time and taking greedily.
Sorting by start and removing the longer of each overlapping pair is the rule most people reach for, and it is wrong on inputs where a long interval overlaps several short ones that do not overlap each other.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ start < end ≤ 1000000000`
Input
The first line contains an integer n.
Each of the next n lines contains two integers: the start and end of one interval.
Output
Print one integer: the fewest intervals that must be removed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.