Merge Intervals
cheatsheet1999 opened this issue · 0 comments
cheatsheet1999 commented
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] overlaps, 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.
/
@param {number[][]} intervals
@return {number[][]}
/
function merge(intervals) {
if (!intervals.length) return intervals
//让每一个数组的第一个数是从小到大排列
intervals.sort((a, b) => a[0] - b[0])
//按顺序拿到一个数组
let prev = intervals.shift()
//res (pass by reference) = prev
let res = [prev]
// Traverse element in intervals, because we need an array with 2 elements, inseatd of a single number in a specific array
for (let curr of intervals) {
// must have a =, otherwise cannot pass [[1,4][4,5]]
if (curr[0] <= prev[1]) {
prev[1] = Math.max(prev[1], curr[1])
} else {
res.push(curr)
prev = curr
}
}
return res
}