4.27.2 — Merge Intervals

LeetCode 56 · Medium · ★ Blind 75

The problem

Merge all overlapping intervals.

[[1,3],[2,6],[8,10],[15,18]]   →  [[1,6],[8,10],[15,18]]
[[1,4],[4,5]]                  →  [[1,5]]     (touching counts as overlapping)

The pattern

Sort by start. That is the first line of almost every interval problem, and here it is what makes the rest trivial.

Once sorted, walk the list carrying the interval you are currently building. For each next interval:

• If it starts at or before the current one ends, they overlap — extend the current end to cover it.
• Otherwise there is a gap, so the current interval is finished. Push it and start a new one.

Why sorting by start is enough. After sorting, any interval that overlaps the one you are building must start within it — anything starting later cannot reach back. So a single "does this start before my end" test catches every overlap, and you never have to look backwards.

The solution

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])           # sort by start
        result = [intervals[0]]

        for start, end in intervals[1:]:
            last_end = result[-1][1]

            if start <= last_end:                     # overlap → extend
                result[-1][1] = max(last_end, end)
            else:                                     # gap → new interval
                result.append([start, end])

        return result

TypeScript

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const result: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    const last = result[result.length - 1];

    if (start <= last[1]) last[1] = Math.max(last[1], end);
    else result.push([start, end]);
  }

  return result;
}

max(last_end, end) is not optional. A fully contained interval like [2,3] inside [1,10] would otherwise shrink the merged interval to [1,3]. This is the bug in this problem, and it only shows up on inputs where one interval swallows another.

start <= last_end uses <= because touching intervals merge here. [1,4] and [4,5] become [1,5].

result[-1][1] = ... mutates the last entry in place, which is cleaner than popping and re-pushing.

In JavaScript, sort() compares as strings by default, so the numeric comparator is mandatory. [[10,20],[9,15]] would sort wrongly without it.

Trace

[[1,3],[2,6],[8,10],[15,18]] — already sorted by start.

interval	last end	overlap?	result
[1,3]	—	—	[[1,3]]
[2,6]	3	2 ≤ 3 → extend to 6	[[1,6]]
[8,10]	6	8 > 6 → gap	[[1,6],[8,10]]
[15,18]	10	gap	[[1,6],[8,10],[15,18]]

Complexity

O(n \log n) time, dominated by the sort. The sweep is O(n).

O(n) space for the output, plus whatever the sort uses.

Sorting is not avoidable here. Without an ordering there is no way to know which intervals might overlap without comparing every pair, which is O(n^2).

Sort by start or by end?

The question that decides most interval problems, so here is the rule:

you want	sort by
merge overlapping intervals	start
the most non-overlapping intervals you can keep	end
the fewest removals to remove all overlaps	end
minimum rooms or maximum concurrency	either, with a sweep or a heap

Sorting by end is the classic activity-selection greedy: finishing earliest leaves the most room for everything after it. That is 4.27.3.

Getting this backwards is the single most common interval mistake.

Where this goes next

• Insert Interval — already sorted, so O(n). 4.27.1.
• Partition Labels — this exact merging, with one interval per letter, hidden inside a string problem. 4.26.7.
• Employee Free Time — merge everyone's busy intervals, then report the gaps.
• Meeting Rooms II — counting overlaps rather than merging them. 4.27.5.
• Real uses — calendar apps, IP range consolidation in routing tables, memory allocator free-list coalescing, and time-series bucketing all run this loop.

What the interviewer will push on

"Why sort by start?" So any overlapping interval must begin inside the one you are building, which makes a single forward test sufficient.

"Why max(last_end, end)?" A contained interval would otherwise shrink the merged range. Give [1,10] and [2,3].

"Do touching intervals merge?" Ask — it decides < versus <=.

"Can you avoid the sort?" Not in general. Without order you would compare every pair.

"What if intervals arrive one at a time?" Repeated merging is O(n) per insertion. An ordered map or an interval tree gives O(\log n).

One thing to volunteer: state the sort-by-start-versus-end rule. It is the one piece of knowledge that makes the whole chapter mechanical, and most candidates rediscover it problem by problem.

Next: 4.27.3 Non-overlapping Intervals — where sorting by end is the answer, and there is a real proof behind it.