Merge Intervals | Programming Challenges

Problem

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. Example: - Input: [[1,3],[2,6],[8,10],[15,18]] - Output: [[1,6],[8,10],[15,18]]

Show solution

Solution (TypeScript)

type Interval = [number, number];

function merge(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: Interval[] = [sorted[0]];

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

    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]);
    }
  }

  return merged;
}

Explanation

Sort intervals by start time. Then iterate and merge into the last interval when there’s an overlap (`start <= lastEnd`), otherwise start a new interval. Sorting dominates: O(n log n) time, O(n) space.