merge-intervals.ts

/**
 * 56. Merge Intervals  (Medium)
 * Link: https://leetcode.com/problems/merge-intervals/
 *
 * Given an array of intervals [start, end], merge all overlapping intervals and
 * return the non-overlapping intervals that cover all the input.
 *
 * Example:
 *   Input:  [[1, 3], [2, 6], [8, 10], [15, 18]]
 *   Output: [[1, 6], [8, 10], [15, 18]]
 *
 * Approach:
 *   Sort intervals by start. Walk them, keeping the last merged interval; if the
 *   next interval starts within it (start <= last.end) extend last.end to the
 *   max, otherwise start a new merged interval. Sorting guarantees overlaps are
 *   adjacent.
 *
 * Time:  O(n log n)  — dominated by the sort.
 * Space: O(n)        — output (or O(1) auxiliary beyond it).
 */
export function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];

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

  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const [start, end] = sorted[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]);
    }
  }

  return merged;
}