JS实现的算法--合并区间

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

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

解：

var merge = function(intervals) {
  if(intervals.length <= 1) {
      return intervals
  }
  
  // 先将数组按照区间最左边的大小顺序排序
  let arr = intervals.sort((a, b) => a[0] - b[0]);
  function unite(arr, i) {
      if(i == arr.length - 1) {
          return arr
      }
      
      // 如果下一个区间的左区间在本区间之间，则合并一次
      if(arr[i][0] <= arr[i + 1][0] && arr[i + 1][0] <= arr[i][1]) {
          arr[i] = [ 
            Math.min(arr[i][0], Math.max(arr[i + 1][0])), 
            Math.max(arr[i][1], Math.max(arr[i + 1][1]))
          ];
          
          // 合并之后删除冗余区间
          arr.splice(i + 1, 1);
      } else {
      
          // 如果没有合并，则找到下一个待合并区间
          i ++;
      }
      return unite(arr, i)
  }
  
  return unite(arr, 0)
};

作者：visa
链接：https://juejin.cn/post/6844903904707084296
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。