Merge IntervalsMedium

Given an array of intervals [start, end], merge all overlapping intervals.

Examples

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

Approach

Repeatedly scanning for any overlapping pair and merging it works but can re-scan the array many times. Sorting by start time first makes one pass enough: once sorted, an interval can only possibly overlap with the interval immediately before it in the result — nothing further back needs re-checking. Walk the sorted list, and either extend the last merged interval (if the current one overlaps it) or start a new one.

Complexity — best & worst case

Repeated-scan approach — time O(n²) worst case

Optimal — time O(n log n), best and worst case are the same — sorting dominates

Optimal — space O(n) for the sorted copy / output

Code

// Given an array of intervals [start, end], merge all overlapping
// intervals and return the merged set.

// --- Brute force: repeatedly scan for any overlapping pair and merge it ---
function mergeBrute(intervals) {
  let merged = intervals.map((i) => [...i]);
  let didMerge = true;

  while (didMerge) {
    didMerge = false;
    outer: for (let i = 0; i < merged.length; i++) {
      for (let j = i + 1; j < merged.length; j++) {
        const [aStart, aEnd] = merged[i];
        const [bStart, bEnd] = merged[j];
        if (aStart <= bEnd && bStart <= aEnd) {
          merged[i] = [Math.min(aStart, bStart), Math.max(aEnd, bEnd)];
          merged.splice(j, 1);
          didMerge = true;
          break outer;
        }
      }
    }
  }
  return merged;
}

// --- Optimal: sort by start time, then merge in a single pass ---
// Once sorted, any overlap can only happen with the interval you just
// placed — you never need to look back further than that.
function merge(intervals) {
  if (intervals.length <= 1) return 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]); // overlaps — extend it
    } else {
      result.push(current); // no overlap — start a new interval
    }
  }
  return result;
}

// --- Example Usage ---
console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1,6], [8,10], [15,18]]
console.log(merge([[1, 4], [4, 5]])); // [[1,5]], touching counts as overlapping