[LeetCode] 56. Merge Intervals

Table of Contents

Description

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

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

Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3: Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Constraints:

• $1 <= intervals.length <= 10^4$
• intervals[i].length == 2
• $0 <= start_i <= end_i <= 10^4$

Approach

Sort the intervals by start time, then iterate and merge when the current interval overlaps the last merged interval.

Solution

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  // Make a shallow copy and sort by start time (ascending) to ensure
  const sortedIntervals = intervals.slice().sort(([a], [b]) => a - b);

  // Result array for merged intervals.
  let mergedIntervals = [];

  for (const [start, end] of sortedIntervals) {
    // Look at the last interval in the result (if any).
    const last = mergedIntervals[mergedIntervals.length - 1] || [];
    const [_, lastEnd] = last;

    // If current interval overlaps or touches the last merged interval,
    // extend the last interval's end to cover the current one.
    if (start <= lastEnd) {
      last[1] = Math.max(lastEnd, end);
      continue;
    }

    // No overlap: append current interval as a new merged interval.
    mergedIntervals.push([start, end]);
  }

  return mergedIntervals;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n \log n)$ due to sorting the intervals.

Space Complexity

The space complexity is $O(n)$ for the output array (in worst case no intervals merge).