Non-overlapping Intervals
mediumGreedy+20 XPTime limit 2s
Remove the minimum number of intervals so that the remaining ones don't overlap. Intervals that only touch (like [1, 2] and [2, 3]) do not overlap.
Input:
- line 1:
n - next
nlines:start end(start < end)
Output: the minimum number of intervals to remove.
Constraints: 1 ≤ n ≤ 10⁵, −5·10⁴ ≤ start < end ≤ 5·10⁴.
Think about it: equivalently, keep as many intervals as possible. Sort by end and greedily keep every interval that starts after the last kept one ends — finishing early leaves the most room (the classic activity selection argument).
Sample input 1
4 1 2 2 3 3 4 1 3
Sample output 1
1
Sample input 2
3 1 2 1 2 1 2
Sample output 2
2
Sample input 3
2 1 2 2 3
Sample output 3
0
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).