← Python roadmap

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.

  1. Sort a copy.
  2. Extend last end if overlapping.
  3. 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?