Leetcode 56 Merge Intervals

Leetcode 56 Merge Intervals

Merge Intervals – 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.

The key to solve this problem is to sort the array first based on the lower bound of each interval. e.g

[[1,4],[0,4]] -> [[0,4],[1,4]]

With this sorted array, we loop through the array once and check each interval to see if it can be merged with the current range that will be pushed to the result array later.

• If yes, we update the current range and move on to the next interval in the array
• If no, we push the current range that we generated to the result array and reassign its value to the current interval

Solution

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0])
    let result = [];
    let currentRange = intervals[0];
    let i = 0;

    while(i < intervals.length) {
        const [ l, r ] = currentRange
        const [ currentL, currentR ] = intervals[i]
        if(currentL >= l && currentL <= r && currentR >= r) {
            currentRange = [l, currentR]
        } else if(currentL > r) {
            result.push(currentRange);
            currentRange = intervals[i]
        }

        i++
    }

    result.push(currentRange)

    return result
};

Depending on your sorting algorithm, the time complexity may differ a little bit. This particular solution uses the built in javascript array sorting function and has a time complexity of O(nlogn) and space complexity of O(1)