合并区间

发表于 分类于 阅读次数： 本文字数： 364 阅读时长 ≈ 1 分钟

以数组 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

要合并重叠的区间，我们需要首先将输入的区间数组按照区间的起始位置进行排序，然后遍历排序后的数组，逐个合并重叠的区间。

以下是解决问题的算法步骤：

  1. 对输入的 intervals 数组按照区间的起始位置进行升序排序。
  2. 初始化一个结果数组 merged 用于存储合并后的区间。
  3. 遍历排序后的 intervals 数组，如果当前区间与 merged 中的最后一个区间有重叠，就合并这两个区间，否则将当前区间添加到 merged 中。
  4. 最后返回 merged 数组作为结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function merge(intervals) {
  if (intervals.length <= 1) {
    return intervals;
  }

  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const currentInterval = intervals[i];
    const lastMergedInterval = merged[merged.length - 1];

    if (currentInterval[0] <= lastMergedInterval[1]) {
      lastMergedInterval[1] = Math.max(
        lastMergedInterval[1],
        currentInterval[1]
      );
    } else {
      merged.push(currentInterval);
    }
  }

  return merged;
}

官方题解