Merge Intervals
Picture
[8,10], [1,3], [2,6] are hard to combine in input order.
Predict
What single value summarizes the merged group while scanning?
Walk through the small example
Its farthest end. Sorting starts makes every future overlap compare against one current farthest end.
Mental model and complete Python solution
After sorting starts, the current merged interval contains everything seen that can still overlap the next interval. Only its start and farthest end matter.
What the function promises: Return merged closed intervals sorted by start. Inputs are pairs with start <= end; touching endpoints merge.
def merge_intervals(intervals):
answer = []
for start, end in sorted(intervals):
if not answer or start > answer[-1][1]:
answer.append([start, end])
else:
answer[-1][1] = max(answer[-1][1], end)
return answer
assert merge_intervals([[8,10],[1,3],[2,6]]) == [[1,6],[8,10]]
assert merge_intervals([]) == []Work and storage: O(n log n) time for sorting and O(n) output space.
When to recognize it: Sorting starts makes every future overlap compare against one current farthest end.
Check before applying it: Endpoint rules differ for closed, open, and half-open intervals; define whether touching counts.
Change one rule
Return the total covered length instead of the intervals.
See what changes
Add each completed merged interval’s length, using the problem’s endpoint convention.
Connect
Sorting: buy useful order: Sorting turns arbitrary overlap into neighboring decisions.
Sweep line: process boundary events: When many event types overlap, scan boundary events instead.