Merge Intervals

The problem

Given a list of intervals [start, end], merge all overlapping intervals and return the non-overlapping result.

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

The answer is [[1, 6], [8, 10], [15, 18]] — [1, 3] and [2, 6] overlap (2 ≤ 3), so they fuse into [1, 6]. The others don't touch anything.

Two intervals a and b (with a starting first) overlap exactly when b.start <= a.end. Intervals that merely touch, like [1, 4] and [4, 5], count as overlapping here.

Approach 1 — Repeated pairwise merging

Compare every pair; merge any overlapping pair and restart until nothing changes.

function merge(intervals) {
  let list = intervals.map((x) => [...x])
  let changed = true
  while (changed) {
    changed = false
    outer: for (let i = 0; i < list.length; i++) {
      for (let j = i + 1; j < list.length; j++) {
        if (list[j][0] <= list[i][1] && list[i][0] <= list[j][1]) {
          list[i] = [
            Math.min(list[i][0], list[j][0]),
            Math.max(list[i][1], list[j][1]),
          ]
          list.splice(j, 1)
          changed = true
          break outer
        }
      }
    }
  }
  return list
}

Time: up to O(n³) in bad cases. It works, but the restarts exist only because the intervals are in arbitrary order.

Approach 2 — Sort, then sweep

Sort by start. Now every interval that could merge with the current group arrives immediately after it — so one pass suffices. Keep the last merged interval; for each new one, either extend it or start fresh.

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0])
  const merged = [intervals[0].slice()]

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

    if (start <= last[1]) {
      last[1] = Math.max(last[1], end) // overlap — extend the group
    } else {
      merged.push([start, end])        // gap — start a new group
    }
  }
  return merged
}

Time: O(n log n) for the sort, O(n) for the sweep. Space: O(n) for the output.

Dry run

intervals = [[8, 10], [1, 3], [15, 18], [2, 6]] — note it starts unsorted.

After sorting: [[1, 3], [2, 6], [8, 10], [15, 18]].

Edge cases

• One interval fully inside another: [1, 10], [2, 3] — the Math.max on the end is what keeps the result [1, 10] instead of wrongly shrinking to [1, 3].
• Touching intervals [1, 4], [4, 5] merge because the check is <=, not <.
• Single interval → returned as-is.
• This sort-then-sweep skeleton also solves Insert Interval, Meeting Rooms, and Non-overlapping Intervals — same idea, different bookkeeping.