Merge Intervals

Loading...LeetCode

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

Constraints:

• 1 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= starti <= endi <= 104

You can solve this problem by first sorting the intervals based on their start times and then merging overlapping intervals. Here's a JavaScript implementation:

function merge(intervals) {
    if (intervals.length === 0) return [];
    
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const currentInterval = intervals[i];
        const lastMergedInterval = merged[merged.length - 1];
        
        if (currentInterval[0] <= lastMergedInterval[1]) {
            lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
        } else {
            merged.push(currentInterval);
        }
    }
    
    return merged;
}

// Test cases
console.log(merge([[1,3],[2,6],[8,10],[15,18]])); // Output: [[1,6],[8,10],[15,18]]
console.log(merge([[1,4],[4,5]]));               // Output: [[1,5]]

This implementation sorts the intervals based on their start times. Then, it iterates through the sorted intervals and merges overlapping intervals. If the current interval overlaps with the last merged interval, it updates the end time of the last merged interval to the maximum of the current and last end times. Otherwise, it adds the current interval to the merged array. Finally, it returns the merged array of non-overlapping intervals.