Merge Intervals

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval.

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval.

Your task is to merge the overlapping intervals and return a new output array consisting of only the non-overlapping intervals.

Statement

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. For example, intervals = [[1,4], [3,6], [7,9]] is sorted in terms of start times 1, 3, and 7.

Your task is to merge the overlapping intervals and return a new output array consisting of only the non-overlapping intervals.

Constraints

• 1 ≤ intervals.length ≤ 10⁴
• intervals[i].length = 2
• 0 ≤ start time ≤ end time ≤ 10⁴

Examples

Example 1

Input Intervals: [1, 5], [3, 7], [4, 6], [6, 8]

Explanation: Intervals [1, 5], [3, 7], [4, 6], [6, 8] are overlapping. Merge them into one interval [1, 8].

Output: [1, 8]

Example 2

Input Intervals: [10, 12], [12, 15]

Explanation: Intervals [10, 12], [12, 15] are overlapping. Merge them into one interval [10, 15].

Output: [10, 15]

Example 3

Input Intervals: [1, 3], [2, 6], [8, 10], [15, 18], [18, 20]

Explanation:

• Intervals [1, 3] and [2, 6] overlap and are merged to [1, 6].
• Intervals [15, 18] and [18, 20] overlap and are merged to [15, 20].

Output: [1, 6], [8, 10], [15, 20]

Solution

To solve this problem, we use the Merge Interval pattern.

• We check for overlapping intervals.
• Two intervals overlap when the closing value of the first interval is greater than or equal to the starting value of the next interval.
• If we find an overlap, we update the closing value. We keep the larger of the two closing values between the overlapping intervals.

Code

function mergeIntervals(intervals) {
  if (!intervals.length) return;

  let result = [];
  result.push([intervals[0][0], intervals[0][1]]);

  let lastAddedInterval, curStart, curEnd, prevEnd;

  for (let i = 1; i < intervals.length; i++) {
    lastAddedInterval = result[result.length - 1];
    curStart = intervals[i][0];
    curEnd = intervals[i][1];
    prevEnd = lastAddedInterval[1];

    if (prevEnd >= curStart) {
      result[result.length - 1][1] = Math.max(curEnd, prevEnd);
    } else {
      result.push([curStart, curEnd]);
    }
  }

  return result;
}