Medium Sort + Merge Intervals
In plain English: Given a list of time ranges that may overlap, combine any overlapping ranges into single ranges.
Sort by start time so overlapping intervals are adjacent. Then sweep left to right — if the current interval overlaps the last merged one, extend it; otherwise start a new merged interval.
Prompt
Given a collection of intervals, merge all overlapping intervals and return the non-overlapping intervals.
Try to write it from scratch before scrolling down.
Solution
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlapping
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# Test: merge([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
# Test: merge([[1,4],[4,5]]) == [[1,5]]