Given a list of intervals, return the minimum number of intervals you must remove so that the remaining intervals do not overlap. Intervals that only touch, like [1,2] and [2,3], do not overlap here.
[1,3] leaves [1,2],[2,3],[3,4].- 1 <= intervals.length <= 10^5
- intervals[i].length == 2
- -5 * 10^4 <= start < end <= 5 * 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every subset to keep is exponential, and a DP over sorted intervals is O(n^2). The greedy idea: sort by end time and keep an interval whenever it starts at or after the end of the last kept one. Why is choosing the earliest end safe? Among all intervals that could come next, the one ending first leaves the most room for the rest; any optimal answer can swap its first interval for this one without causing a new overlap. So the greedy keeps the maximum number, and we remove the others.
Algorithm
- Sort intervals by end.
- Set
prevEndto the end of the first interval andremoved = 0. - For each next interval: if
start < prevEnd, it overlaps, soremoved += 1. - Otherwise keep it and set
prevEnd = end. Returnremoved.
O(n log n)Space: O(1) extra besides the sortclass Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: x[1]) # by end removed = 0 prev_end = intervals[0][1] for s, e in intervals[1:]: if s < prev_end: removed += 1 # overlaps the last kept interval else: prev_end = e # keep it return removed