HARD Lab · Intervals · 49

56. Merge Intervals

Sort the intervals by start value first — that single step guarantees any overlap only happens with the immediately preceding merged interval, enabling a clean O(n) sweep instead of an O(n²) nested comparison.

● MediumSortingIntervalsTypeScript

PROBLEM What we're solving

Given an array of intervals [[start, end], …], merge all overlapping intervals and return the result. Two intervals overlap when one starts at or before the other ends.

Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] because [1,3] and [2,6]overlap (2 ≤ 3), so they fuse into [1,6]. The remaining two pairs have gaps, so they stay separate.

KEY IDEA Sorting by start collapses the problem to a single sweep

Insight → If you sort by start value first, then every interval can only overlap with the interval that was most recently added to the result list — never an earlier one. So you only need to compare current.start against last.end. One forward pass, no backtracking.

RECIPE Sort, sweep, extend-or-push

  • 1 · Sort by start. intervals.sort((a, b) => a[0] - b[0]). This is the enabling step — overlaps become local (adjacent).
  • 2 · Init result. Push the first sorted interval directly; it has nothing to overlap with yet.
  • 3 · Sweep. For each subsequent interval [start, end]:
    • If start <= last.end — overlap: update last.end = max(last.end, end). Use maxbecause a fully-contained interval wouldn't extend the end.
    • Otherwise — gap: push [start, end] as a new entry.
  • 4 · Return the result array.
Classic confusion → forgetting Math.max when extending. If the new interval is fully contained within the last merged one (e.g. [1,10] followed by [2,5]), a naive last.end = end would incorrectly shrink the result to [1,5].

COST Complexity & alternatives

Brute force (nested loops)
O(n²)
Compare every pair; no sort needed but very slow.
Sort + sweep
O(n log n)
Dominated by sort; O(n) extra space for output.

The sweep itself is O(n) — each interval is pushed or merged exactly once. Total is O(n log n) for the sort. In-place mutation of the input is possible but messy; the idiomatic approach uses a separate output array.

Pattern transfer → the same sort-then-sweep skeleton applies to Insert Interval (LC 57), Non-overlapping Intervals(LC 435), and Meeting Rooms I&II — sort events by start and process them in order.

RUN IT Sort by start, then sweep and merge

step 0 / 6
STARTInput: [1,3], [2,6], [8,10], [15,18]. First we sort by start value — that is the key step that makes a single sweep possible.
input (unsorted)1-302-618-10215-183
State
[]
result
sort
phase
current intervalmerged resultnot yet processed
slowfast

TYPESCRIPT The solution, annotated

mergeIntervals.ts
function merge(intervals: number[][]): number[][] {
  // Sort by start so any overlap must be with the immediately previous merged interval
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [];

  for (const [start, end] of intervals) {
    if (merged.length === 0) {
      merged.push([start, end]);
      continue;
    }

    const last = merged[merged.length - 1];

    if (start <= last[1]) {
      // Overlapping: extend the end if needed
      last[1] = Math.max(last[1], end);
    } else {
      // Gap: start a fresh interval
      merged.push([start, end]);
    }
  }

  return merged;
}

Reading it block by block

Line 3 — sort by start. This is the entire trick: after sorting, any interval that overlaps [start, end]must be the one immediately before it in the sorted list. A later interval can't start earlier, so it can't retroactively extend an already-closed gap.
Lines 7–10 — first interval. The result list is empty, so push [start, end] unconditionally and continue to the next.
Lines 12–13 — peek at the last merged interval. We only need the tail of the result; earlier entries are final and will never change again (because sort guarantees no future interval starts before the current one).
Lines 15–17 — overlap branch. start <= last[1] means the current interval begins inside or at the boundary of the last merged one. Extend the end with Math.max(last[1], end) — the max handles full containment (e.g. [1,10] swallowing [2,5]).
Lines 18–20 — gap branch. start > last[1]means there's a real gap. The previous merged interval is now closed forever; push a fresh one.
Line 24 — return.Every interval has been processed exactly once: O(n) sweep after an O(n log n) sort.
Complexity → O(n log n) time (dominated by sort), O(n) space for the output array. The sweep itself is O(n) — each interval enters and leaves the "last merged" slot at most once.

INTERVIEWFollow-ups they'll ask

  • "What if intervals can have negative starts?" No change — the sort comparator works for all integers.
  • "Can you do it in-place?" Yes: overwrite the input array with merged intervals using a write pointer. Saves a separate array but complicates the code and is rarely worth it.
  • "Insert Interval next?" A twist: one new interval arrives and must be merged into an already-sorted list. Split into three phases: copy left (no overlap), merge middle (overlap), copy right.
  • "Non-overlapping Intervals (min removals)?" Sort by end, greedily keep the interval with the earliest end — classic greedy scheduling. The sort step is the same key move.
  • "Meeting Rooms II (min rooms)?" Split into start/end event arrays, sort both, sweep with two pointers or a min-heap to track concurrent meetings.

MNEMONIC The one-liner

"Sort starts, sweep once: overlap → stretch the end; gap → push fresh."

TRIGGERS When you see ___ → reach for ___

"merge overlapping intervals"sort by start → sweep last.end
start ≤ last endoverlap: extend last[1] = max(last[1], end)
start > last endgap: push new interval
"insert/remove/count intervals"same sort-by-start skeleton

SKELETON The reusable shape

skeleton.ts
function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);   // sort by start
  const merged: number[][] = [];

  for (const [start, end] of intervals) {
    const last = merged[merged.length - 1];
    if (!last || start > last[1]) {
      merged.push([start, end]);            // no overlap: new interval
    } else {
      last[1] = Math.max(last[1], end);     // overlap: extend end
    }
  }

  return merged;
}

FLASHCARDS Tap to flip

Why sort by start before merging?
It makes overlaps local: any overlapping interval must be adjacent in sorted order, enabling a single O(n) sweep.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the time complexity of the sort-then-sweep merge algorithm?
QUESTION 02
After sorting, you compare current.start against last.end. What does current.start <= last.end mean?
QUESTION 03
You have merged [1,10] and the next sorted interval is [3,5]. What should the merged list contain after processing [3,5]?
QUESTION 04
Why is sorting by start the critical enabling step?
QUESTION 05
Input: [[1,4],[4,5]]. What is the output?
QUESTION 06
Which of these is NOT a problem that directly reuses the sort-by-start sweep pattern?
QUESTION 07
Space complexity of the standard merge-intervals solution (separate output array)?