Overview

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the ranges.

Implement mergeIntervals(intervals).

Constraints

• Each interval is a two-element array [start, end] where start ≤ end.
• Input may be unsorted.
• Return merged intervals sorted by start time.
• Aim for $O(n \log n)$ time (dominated by sorting).

Examples

mergeIntervals([[1,3],[2,6],[8,10],[15,18]]);
// → [[1,6],[8,10],[15,18]]

mergeIntervals([[1,4],[4,5]]);
// → [[1,5]]  — touching intervals merge

mergeIntervals([[1,4],[0,4]]);
// → [[0,4]]

Notes

• Sort intervals by start time. Then iterate: if the current interval overlaps with the last merged one (its start ≤ previous end), extend the previous end. Otherwise, push a new interval.
• Two intervals [a,b] and [c,d] overlap if c ≤ b (after sorting a ≤ c).
• Edge cases: single interval, all overlapping, none overlapping.

Solution

function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals;

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

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

  return merged;
}

Resources

• Merge Intervals — LeetCode
• Interval Scheduling — Wikipedia