Given a collection of intervals, find the minimum number of intervals you must remove so that the remaining intervals do not overlap.
For example, given [[1,2],[2,3],[3,4],[1,3]], you need to remove 1 interval ([1,3]) to make the rest non-overlapping. The answer is 1.
Another example: [[1,2],[1,2],[1,2]] requires removing 2 intervals. The answer is 2.
Explain your approach, why it works, and analyze the time and space complexity.
How to approach it
- Hint 1
This is equivalent to finding the maximum number of non-overlapping intervals and subtracting from the total.
- Hint 2
Sort intervals by end time. Why might sorting by end time be better than sorting by start time?
- Hint 3
Greedily pick the interval that ends earliest -- this leaves the most room for future intervals.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.