Medium Greedy Choice Greedy
In plain English: Remove the fewest intervals so that none of the remaining ones overlap.
Sort by end time and greedily keep intervals that start after the previous one ends — this maximizes non-overlapping intervals (classic activity selection).
Prompt
Given a list of intervals, find the minimum number of intervals to remove so that the remaining intervals do not overlap.
Try to write it from scratch before scrolling down.
Solution
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # keep this interval
else:
count += 1 # remove this interval (overlaps)
return count
# Test: erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]) == 1
# Test: erase_overlap_intervals([[1,2],[1,2],[1,2]]) == 2