前端刷题路-Day71：合并区间（题号56）-一一网

这是我参与8月更文挑战的第4天，活动详情查看：8月更文挑战

合并区间（题号56）

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
复制代码

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
复制代码

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

链接

leetcode-cn.com/problems/me…

解释

这题啊，这题是经典没想到。

思维被限制住了，笔者一直试图在原数组的基础上进行操作，疯狂尝试和修改，但修改的时候一直没办法控制好修改范围，导致有的区间并不能成功的被覆盖掉。

其实主要想法都是没问题的，用一个变量来记录当前的区间值，后续继续查找有无区间值在当前范围内，如果有，利用splice去掉数组中的元素，否则查找下一个元素。

主要逻辑是这样，可问题出现了，你怎么保证后面的元素都是在前面的区间值内呢？或者说怎么保证区间的排列规则呢？如果不保证规则，那就只能每次都查找剩余的所有数据才能得出结果，这显然是浪费时间的。

所以，需要在一开始的时候对区间进行排序，排序的元素就是每个区间的开始元素，为什么要用开始元素来进行排序？因为开始元素决定了一个区间的起点，所以排序的结果必能保证第一个元素的是所有区间中开始元素最小的一个，也就是说它代表了所有区间的开始位置。

如此，只需要更新区间的结束元素即可，如果下一个区间的开始元素比当前区间的结束元素大，那么就需要修改当前区间的结束元素为下一个区间的结束元素和当前区间的结束元素中的最大值。

这里取最大值是因为下一个区间有可能完全被上一个区间覆盖，如果默认去下一个区间的结束元素，有可能会出现修改错误的情况。

整体逻辑就是这样，下面看看代码。

自己的答案（排序）

事先说明，这个答案是笔者看了官方答案后根据自己的代码改写出来的，第一时间确实没想到给区间排序的操作：

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  let i = 1;
  let active = intervals[0][1]
  while (i <= intervals.length - 1) {
    const cur = intervals[i]
    if (cur[0] <= active) {
      active = Math.max(active, cur[1])
      intervals[i - 1][1] = active
      intervals.splice(i, 1)
    } else {
      active = cur[1]
      i++
    }
  }
  return intervals
};
复制代码

整体思路和上面说的一样，利用active变量来存储当前区间的结束元素，之后判断下一个区间的开始元素是否比active小，如果小，那必然是在当前区间内的，因为区间都是根据开始元素进行排序的，后面区间的开始元素必然大于等于前面区间的开始元素。

符合条件后修改结束元素，并且去掉数组中的元素；否则更新active，进入下一次循环。

更好的方法（排序）

下面是官方答案，整体思路和上面差不多，但官方是往一个新数组中push更新后区间?：

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  let prev = intervals[0]
  let result = []
  for(let i =0; i<intervals.length; i++){
    let cur = intervals[i]
    if(cur[0] > prev[1]){
      result.push(prev)
      prev = cur
    }else{
      prev[1] = Math.max(cur[1],prev[1])
    }
  }
  result.push(prev)
  return result
};
复制代码