Merge Intervals

Merge every pair of overlapping ranges.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Merge Intervals: Sort ranges by start; compare each range with the last merged end, extending on overlap or appending on a gap.

Input and goalMerge every pair of overlapping ranges.

Sort the concrete inputInput [[8,10],[1,3],[2,6],[15,18]] becomes [[1,3],[2,6],[8,10],[15,18]], so possible overlaps are adjacent.

1: [1,3]

2: [2,6]

3: [8,10]

4: [15,18]

ordersorted by start

Recognize it

Use it when arbitrary ranges must be coalesced by overlap; sorting by start guarantees that any range able to overlap the current merged component appears before a later gap.

Keep true

Before each current interval, merged is sorted, disjoint, and exactly covers all processed ranges; only merged[-1] can overlap current because starts are nondecreasing.

Reuse it

Sorting can turn a global overlap problem into a local frontier check: preserve a completed prefix and keep only the final component open for possible extension.

Pattern: Sort by start, then scan.

Simple idea: Compare each range with the last merged range. Overlap extends the last end. No overlap starts a new result range.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
   if not intervals:
      return []

   ordered = sorted(intervals)
   merged = [ordered[0].copy()]

   for start, end in ordered[1:]:
      if start <= merged[-1][1]:
         merged[-1][1] = max(merged[-1][1], end)
      else:
         merged.append([start, end])
   return merged

Cost: $O(n\log n)$ time and $O(n)$ answer space.