Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]] 
Output: [[1,6],[8,10],[15,18]]
Example 2:
Input: [[1,4],[4,5]] 
Output: [[1,5]]

Discussion
If we can assume intervals input are sorted by when the interval starts (the first digit of the interior array), we can use the following algorithm:

• if starting interval is before the max ending interval we’ve seen so far, it’s a separate interval
  • we need to save the expanded interval we’ve seen so far
  • we need to update our tracking variables so it’s reset and ready for next interval
• if starting interval is before or equal to the max ending interval we’ve seen so far, it’s an overlapping interval
  • we need to expand the max interval if the ending interval of this overlapping interval is greater than what we’ve seen so far

Sort Intervals by Start
However since we haven’t been told we can assume that the intervals are sorted, we can sort the intervals first.

    //sort by start; should be done in function
    const cb=(a,b) => {
        if (a[0]<b[0]) {
            return -1;
        }
        else {
            return 1;
        }
    }
    intervals=intervals.sort(cb);

Main Code
Now we just need to keep track of what intervals we’ve seen so far and update accordingly. We only need 3 new variables here, start, max and result. We use a cur variable just for easier reading.

var merge = function(intervals) {
    //sort by start [see code above!]
    
    if (intervals.length===0) {
        return [];
    }
    
    let start=intervals[0][0];
    let max=intervals[0][1];
    let result=[];
    for (let i=0;i<intervals.length;i++) {
        let cur=intervals[i];
        if (max>=cur[0]) { //within interval
            max=Math.max(intervals[i][1],max); //update max
            continue;
        }
        else { //not within interval so start new interval
            result.push([start,max]); //save old interval
            start=cur[0];
            max=cur[1];
        }
    }
    result.push([start,max]); //save last result
    return result;
};

Complexity
The sort is nlog(n).
The array scan is n.
Therefore big O notation for time complexity is O(n)=n*log(n)
In terms of space, we have O(1) space since the 3 variables we use to keep track of things don’t scale with the size of the array input.