Merge overlapping intervals

Given a set of intervals, merge all the overlapping intervals and return the non-overlapping list.

Examples

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

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Method 1: Merge overlapping intervals using stack.

Conceptually this is how it works.

• First, sort the array in the ascending order based on the start time.
• We will use a stack to track the intervals and merge them. Add the first interval from the sorted one to the stack.
• Then pop the first result and compare it with the remaining values of the stack if it is overlapping or not.
• If both are overlapping then merge the intervals, else add both back to the stack.

const merge = (intervals) => {
    //If empty
    if (!intervals.length) return [];
    
    //Sort the array based on the start time
    intervals.sort(([i, j], [m, n]) => m - i || n - j);
    
    //stack 
    let stack = []
    
    //Iterate the intervals
    while (intervals.length) {
        //Get the start and end
        let [start1, end1] = intervals.pop();
      
        // squeeze adjacent intervals
        while (intervals.length) {
            let [start2, end2] = intervals.pop();
          
            // check if overlapping -> merge
            if (start2 <= end1){ 
              [start1, end1] = [start1, Math.max(end1, end2)];
            }
            else {
                //Push original
                stack.push([start1, end1]);
                //Replace with next one
                [start1, end1] = [start2, end2];
            }
        }
        
        //Push the merged interval
        stack.push([start1, end1]);
    }
  
    return stack;
};

Input:
const arr = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(arr));

[[1,6],[8,10],[15,18]]

Time complexity: O(nlog(n) + n ^ 2) = O(n^2).
Space complexity: O(n).

---

Method 2: O(nlogn) solution.

We can implement the above solution without using a stack and in O(nlogn) time. All we have to do is correctly maintain the order of iteration.

• Sort the array in ascending order based on the start time of each interval.
• Iterate for all the intervals except for last.
• In each iteration compare with next interval and if there is a overlap, merge them.
• After merging replace the current two intervals with the new merged interval and reduce the counter of iteration so that for next iteration this merged interval and next one will be compared.

const merge = (intervals) => {
    //Sort the intervals based on the start time
    intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    
    //Iterate the intervals
    for(let i = 0; i < intervals.length-1; i++) {
        //Get the start and end time of each interval
        const [start1, end1] = intervals[i];
        const [start2, end2] = intervals[i+1];
        
        //if there is overlapp then merge the index
        if(start2 <= end1) {
          
            //Get the min of start of interval and max of end.
            const newInterval = [Math.min(start1, start2), Math.max(end1, end2)];
          
            //Add the new interval to the array
            intervals.splice(i, 2, newInterval);
          
            //keep the i at the same index to continue the comparing
            i--;
        }
    }
   
    //Return the merged intervals.
    return intervals;
};

Input:
const arr = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(arr));

[[1,6],[8,10],[15,18]]

Time complexity: O(nlogn).
Space complexity: O(1).