Merge Intervals

Difficulty: Medium

You're given a list of intervals, in no particular order, where each interval is a start and end pair. Some of them overlap — meaning they share at least one point in time. Combine every group of overlapping intervals into a single interval that spans all of them, and return the resulting list.

Two intervals that merely touch (one ends exactly where the other begins) are treated as overlapping here, since that shared point belongs to both.

Examples

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

[1,3] and [2,6] share the range 2-3, so they merge into [1,6]. The other two don't touch anything.

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

[1,4] and [4,5] touch at the point 4, so they merge into [1,5].

Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]

[2,3] is completely contained inside [1,4], so it disappears into it.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start <= end <= 10^4

Approach

A direct way to solve this is to repeatedly scan the list for any two intervals that overlap and merge them, starting over each time you find a merge, until nothing overlaps anymore. It's correct, but slow, because you keep re-checking pairs that were never going to overlap in the first place.

The key realization is that if you first sort the intervals by start time, an overlap can only ever happen between an interval and the one right before it in that sorted order — nothing further back needs to be reconsidered. That turns the problem into a single scan: keep a "current merged interval," and every time the next interval's start creeps back into it, stretch it to cover that interval too; otherwise, close it out and start a new one.

Solutions

Brute Force — Repeated Pairwise Merging

Keep scanning the list for any pair of intervals that overlap. Whenever you find one, merge it into a single interval, remove the two originals, and start scanning again from the top. Stop once a full pass finds nothing left to merge.

function merge(intervals) {
  const result = intervals.map((iv) => [...iv]);
  let mergedSomething = true;

  while (mergedSomething) {
    mergedSomething = false;
    for (let i = 0; i < result.length && !mergedSomething; i++) {
      for (let j = i + 1; j < result.length; j++) {
        const overlaps = result[i][0] <= result[j][1] && result[j][0] <= result[i][1];
        if (overlaps) {
          result[i][0] = Math.min(result[i][0], result[j][0]);
          result[i][1] = Math.max(result[i][1], result[j][1]);
          result.splice(j, 1);
          mergedSomething = true;
          break;
        }
      }
    }
  }

  return result;
}

Time: O(n^3) in the worst case — each of up to n merge passes rescans all O(n^2) pairs · Space: O(n) for the working copy

Optimal — Sort by Start, Then Scan

Sort the intervals by their start value. Now walk through them left to right, keeping the last interval you've added to the answer. If the next interval's start is at or before that last interval's end, they overlap (or touch), so stretch the last interval's end to cover it. Otherwise, the next interval can't reach back to anything already merged, so it starts a fresh entry in the answer.

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

  for (let i = 1; i < sorted.length; i++) {
    const last = result[result.length - 1];
    const current = sorted[i];

    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      result.push(current);
    }
  }

  return result;
}

Time: O(n log n) — dominated by the sort, the scan itself is O(n) · Space: O(n) for the sorted copy and result