cheatsheet1999/FrontEndCollection

Merge Intervals

cheatsheet1999 opened this issue · 0 comments

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
}