Merge Intervals

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 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] overlaps, 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.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Solution

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]); // sort by start
    const stack = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const prev = stack[stack.length - 1];
        const cur = intervals[i];
        if (cur[0] <= prev[1]) { // overlap => merge the two intervals
            prev[1] = Math.max(cur[1], prev[1]);
        } else { // no overlap
            stack.push(cur);
        }
    }
    return stack;
};

We will implement a greedy solution. First, we sort intervals by the start time. Next, we iterate through all intervals. For two consecutive intervals, if the first interval's end time is greater then the second interval's start time, it must mean the two intervals overlap, and so we can merge them. Repeat this process until all overlapping intervals are merged.