#56. 合并区间

LeetCode 原题链接

#题目描述

给定一个区间数组 intervals，其中 intervals[i] = [start, end] 表示一个闭区间。

请合并所有重叠的区间，并返回一个不重叠的区间数组。返回结果中需要覆盖输入中的所有区间。

示例：

输入：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
输出：[[1, 6], [8, 10], [15, 18]]
解释：[1, 3] 和 [2, 6] 重叠，合并为 [1, 6]。

#题型判断

这是一道区间合并题。

题目需要判断多个区间是否重叠，并把重叠区间合并。原始数组不保证有序，如果直接两两比较会比较复杂。

处理区间重叠问题时，常见做法是先按照区间左端点排序。排序后，可能和当前区间重叠的区间一定会连续出现，只需要从左到右维护已经合并好的最后一个区间即可。

#核心思路

先将所有区间按照起点 start 从小到大排序。

排序后，从左到右遍历每个区间：

1. 如果结果数组 ans 为空，直接把当前区间加入结果。
2. 如果当前区间的起点 start 大于结果数组最后一个区间的终点 lastEnd，说明二者不重叠，当前区间可以直接加入结果。
3. 如果当前区间的起点 start 小于等于 lastEnd，说明二者重叠，需要把最后一个区间的右端点更新为更大的那个：

lastEnd = Math.max(lastEnd, end)

为什么只需要和结果数组最后一个区间比较？

因为区间已经按起点排序，当前区间的起点不会小于前面区间的起点。如果它不能和最后一个已合并区间重叠，就更不可能和更早的区间重叠；如果它能重叠，也只需要扩展最后一个合并区间。

#示例步骤图解

以 intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] 为例。

排序后仍然是：

[[1, 3], [2, 6], [8, 10], [15, 18]]

最终返回：

[[1, 6], [8, 10], [15, 18]]

再看一个需要连续扩展右边界的例子：

intervals = [[1, 4], [2, 3]]

排序后还是 [[1, 4], [2, 3]]。遍历到 [2, 3] 时，2 <= 4，说明重叠，但右端点不需要变大：

max(4, 3) = 4

所以结果是 [[1, 4]]，不能错误地改成 [[1, 3]]。

#变量与区间含义

• intervals：输入区间数组，每个元素是 [start, end]。
• ans：已经合并完成的区间数组。
• start：当前遍历区间的左端点。
• end：当前遍历区间的右端点。
• last：ans 中最后一个区间，也就是当前最可能和新区间合并的区间。
• last[1]：最后一个已合并区间的右端点。

ans 的含义是：遍历到当前区间之前，所有已经处理过的区间合并后的结果。

#推进规则

遍历当前区间 [start, end] 时：

• 如果 ans.length === 0，直接加入当前区间。
• 否则取出最后一个合并区间 last = ans[ans.length - 1]。
• 如果 start > last[1]，说明当前区间和 last 不重叠，直接加入 ans。
• 如果 start <= last[1]，说明当前区间和 last 重叠，更新 last[1] = Math.max(last[1], end)。

这里判断重叠时使用的是 start <= last[1]，因为题目中的区间是闭区间，例如 [1, 4] 和 [4, 5] 在端点 4 处相交，需要合并为 [1, 5]。

#边界条件与易错点

• 空数组：如果 intervals.length === 0，直接返回 []。
• 只有一个区间：排序和遍历后仍返回它本身。
• 必须先按左端点排序，否则只和最后一个区间比较是不可靠的。
• 合并时右端点要取最大值，不能直接赋值成当前区间的 end。
• 判断闭区间重叠要用 start <= last[1]，不是 start < last[1]。
• Array.prototype.sort 会原地修改 intervals。如果题目或业务要求保留原数组，可以先复制一份再排序。

#代码实现

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  if (intervals.length === 0) {
    return [];
  }

  // 先按区间左端点从小到大排序。
  intervals.sort((a, b) => a[0] - b[0]);

  const ans = [];

  for (const [start, end] of intervals) {
    if (ans.length === 0) {
      ans.push([start, end]);
      continue;
    }

    const last = ans[ans.length - 1];

    if (start > last[1]) {
      // 当前区间和最后一个合并区间不重叠，直接加入结果。
      ans.push([start, end]);
    } else {
      // 当前区间和最后一个合并区间重叠，扩展右边界。
      last[1] = Math.max(last[1], end);
    }
  }

  return ans;
};

#复杂度分析

• 时间复杂度：O(n log n)，其中 n 是区间数量。主要开销来自排序，遍历合并是 O(n)。
• 空间复杂度：O(log n) 或 O(n)。排序本身可能使用递归栈或额外空间；如果不考虑返回结果数组，额外空间通常取决于排序实现。