Medium Greedy End-Sort Intervals
In plain English: Remove the fewest time ranges so that none of the remaining ones overlap.
Sort by end time (greedy activity selection). Always keep the interval that ends earliest — it leaves the most room for future intervals. Count how many you have to skip.
Prompt
Given an array of intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.
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
removals = 0
prev_end = float('-inf')
for start, end in intervals:
if start < prev_end: # overlap
removals += 1 # remove this one (it ends later)
else:
prev_end = end # keep this one
return removals
# Test: erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]) == 1
# Test: erase_overlap_intervals([[1,2],[1,2],[1,2]]) == 2