https://leetcode-cn.com/problems/merge-intervals/
点击查看【bilibili】

题目

给出一个区间的集合，请合并所有重叠的区间。

示例

  1. 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
  2. 输出: [[1,6],[8,10],[15,18]]
  3. 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
  5. 输入: intervals = [[1,4],[4,5]]
  6. 输出: [[1,5]]
  7. 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解答

image.png
1将数组中的区间按照起始位置排序
2.用curr数组记录当前合并的最大区间,遍历数组中的每一个区间,
如果当前区间的起始位置小于等于curr的终点位置,则可以继续合并,
所以合并 并更新curr的起始和终止位置。
如果当前区间的起始位置大于curr的终止位置,则无法合并。
所以将curr加入到result里,并用当前的区间替换curr的值

答案

  1. /**
  2.  * @param {number[][]} intervals
  3.  * @return {number[][]}
  4.  */
  5. var merge = function(intervals) {
  6.     if(intervals.length < 2 ) {
  7.         return intervals
  8.     }
  9.     // 数组进行排序，如果第一个值相同，比较第二个值
  10.     intervals.sort(function(a,b){
  11.         return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
  12.     })
  14.     let curr = intervals[0]  // 建立变量，初始化数组第一个
  15.     let result = []
  16.     // 循环数组进行比较
  17.     for(let interval of intervals) {
  18.         // 如果curr末位 大于等于 当前项的首位，那么合并两个项，取最大值作为末位
  19.         if(curr[1] >= interval[0]) {
  20.             curr[1] = Math.max(curr[1], interval[1])
  21.         // 否则没有重合区间，将curr值添加到结果，curr指向当前项
  22.         }else {
  23.             result.push(curr)
  24.             curr = interval
  25.         }
  26.     }
  27.     // 如果循环完curr还有值，也就是没有走push阶段，进行合并了，
  28.     // 但是没有加到结果里，加入到结果
  29.     if(curr.length!==0) {
  30.         result.push(curr)
  31.     }
  33.     return result
  34. };