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.
Pseudocode
- sort array in ascending min val
- for loop to merge
- what are conditions to merge?
- push non merge/overlaps to result
Solution
function merge(intervals) {
if (!intervals.length) {
return intervals;
}
// if start interval isn't the same, sort using the start interval, otherwise sort using end interval
intervals.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
// console.log(intervals)
var prev = intervals[0];
var res = [prev];
for (var curr of intervals) {
// if start of current interval is smaller than previous end
if (curr[0] <= prev[1]) {
// merge to the largest end interval either previous or current
prev[1] = Math.max(prev[1], curr[1]);
// else push and reassign prev and curr
} else {
res.push(curr);
prev = curr;
}
}
return res;
}
