Skip to main content

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] 可被视为重叠区间。

答案

思路：

先排序（根据区间的第一项）
声明新数组 result[],放入区间第一项
从 1 开始遍历区间向前对比
- 声明上一项const pre = result[result.length - 1]
- 当前区间[0]与上一项区间[1]重叠，则找到当前区间和上一区间最大项，替换pre[1]
- 不重叠则推入 result 数组

var merge = (intervals) => {
  // 1. 先排序（根据区间的第一项）
  // 按照起始位置排序，避免[[1,4],[0,4]]无法匹配
  intervals.sort((a, b) => a[0] - b[0]);
  // 2. 声明新数组 result[],放入区间第一项
  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    // 前数据
    const pre = result[result.length - 1];
    // 后数据[0] 与 前数据[1]对比
    //(不能使用前数据[1]与后数据[0]对比有缺陷，避免[[1,4],[2,3]]无法匹配)
    if (intervals[i][0] <= pre[1]) { // 重叠说明在区间中
      // Math.max判断最大位
      pre[1] = Math.max(intervals[i][1], pre[1]);
    } else { // 不重叠 不在区间中
      result.push(intervals[i]);
    }
  }
  return result;
};

// var intervals = [[1,4],[0,4]]
// var intervals = [[1,4],[2,3]]
var intervals = [[1,3],[2,6],[8,10],[15,18]]

console.log(merge(intervals))

答案