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