Merge closed overlapping intervals
AdvancedMid-level · 3–5 yearsIntervals
Python 3.10+; standard library only. GIL discussion refers to conventional CPython builds, not optional free-threaded builds.
Problem statement
Return sorted disjoint closed intervals covering exactly the input intervals; touching endpoints merge.
Consolidate maintenance windows.
Input: List of [start,end] integer pairs.
Output: Sorted merged list.
- start <= end.
- Input must not be mutated.
- 0 <= n <= 100000.
Sample 1
Input: [[1,3],[2,6],[8,10]] Output: [[1,6],[8,10]]
The first two overlap.
Sample 2
Input: [[1,2],[2,3]] Output: [[1,3]]
Closed intervals touch at 2.
Brute-force solution
Repeatedly find overlapping pairs and merge them until no overlap remains; worst case requires repeated scans.
O(n log n)
def merge_intervals(intervals):
result=[]
for start,end in sorted(intervals):
if result and start<=result[-1][1]:
result[-1][1]=max(result[-1][1],end)
else:
result.append([start,end])
return result
print(merge_intervals([[1,3],[2,6],[8,10]]))
Optimized solution
Sort by start. Only the last merged interval can overlap the next interval.
- Sort a copy.
- Extend last end if overlapping.
- Otherwise append a new interval.
def merge_intervals(intervals):
result=[]
for start,end in sorted(intervals):
if result and start<=result[-1][1]:
result[-1][1]=max(result[-1][1],end)
else:
result.append([start,end])
return result
print(merge_intervals([[1,3],[2,6],[8,10]]))
Complexity analysis
Time: O(n log n)
Auxiliary space: O(n)
Test cases
- Empty input.
- Contained interval.
- Touching endpoints.
assert merge_intervals([[1,3],[2,6],[8,10]])==[[1,6],[8,10]]
assert merge_intervals([[1,2],[2,3]])==[[1,3]]
assert merge_intervals([])==[]Common mistakes
- Shrinking the end when the next interval is contained.
- Mutating the caller's list.
Key takeaways
- Sort by start.
- Use max of ends.
- State endpoint semantics.
Follow-up challenges
- How do half-open intervals change touching behavior?
- How would online insertion work?