4.27.2 — Merge Intervals

LeetCode 56 · Medium · ★ Blind 75

The problem

Merge all overlapping intervals.

Restating the Problem: You are given an array of intervals where each interval has a start and end time. Some of these intervals may overlap. Your task is to combine all overlapping intervals into single, larger intervals, returning an array of mutually exclusive (non-overlapping) intervals that cover the exact same time spans as the original input.

• Constraints to note: The array length is up to 10^4, so an O(n^2) approach might TLE, guiding us toward an O(n \log n) sorting-based approach.
• Edge cases: The input array might be empty or have only one interval. Intervals can be fully contained within other intervals (e.g., [1, 10] and [2, 3]).

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

Brute Force Approach

A naive approach would be to start with the first interval, scan the entire list to find any overlapping interval, merge them, and repeat this process from the beginning until a full pass reveals no new overlaps. In the worst case, every merge requires rescanning the remaining intervals, leading to an O(n^2) time complexity. This is highly inefficient because it lacks an ordered way to check overlaps.

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.

Code Walkthrough:

• Sorting: We first sort the intervals based on their start times.
• Initialization: We initialize a result list and place the first interval into it.
• Iteration: We loop through the remaining intervals starting from index 1.
• Overlap Check (start <= last_end): For each interval, we check if its start is less than or equal to the end of the last interval in our result list. Because the intervals are sorted by start time, we know its start time is \ge the last interval's start time. We only need to check if it starts before the last one ends.
• Merge or Add: If it overlaps, we extend the end of the last interval in result to be the max of both ends. If it doesn't overlap, we have found a distinct non-overlapping interval, so we simply append it to result.
• Return: Finally, we return the result list.

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

• Time Complexity: O(n \log n). Sorting the array dominates the time complexity. The subsequent linear scan takes O(n) time.
• Space Complexity: O(n) or O(\log n) extra space depending on the sorting algorithm used by the language, plus O(n) to store the output.

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.