合并区间怎么做？为什么要先按区间左端点排序？

知识点详解：维护一个合并结果，怎样覆盖整个区间集合

左端点排序，保证后面不会突然出现更早的起点

咱们假设区间是 [1, 3]、[2, 6]、[8, 10]、[9, 12]。按左端点排序以后，扫描方向就和时间轴方向一致。

维护 [1, 3]，看到 [2, 6] 时，2 没有超过 3，因此合成 [1, 6]。看到 [8, 10] 时，8 超过 6，说明前面的合并区间可以确定并保存。

为什么可以确定？因为后面区间的左端点不会比 8 更小，它们不可能重新伸回去连接 [1, 6]。这是排序提供的关键保证，不只是让数组看起来整齐。

合并区间原题采用闭区间重叠规则。下面实现遵循这份约定。

右端点取最大，避免被包含区间缩短

当前区间是 [1, 10]，下一个是 [2, 3]。它们重叠，但合并后仍然是 [1, 10]，不能直接把右端点替换为 3。

function mergeIntervals(input: number[][]): number[][] {
  if (input.length === 0) return [];
  const intervals = input.map(([a, b]) => [a, b])
    .sort((x, y) => x[0] - y[0]);
  const result: number[][] = [];
  let [start, end] = intervals[0];
  for (const [left, right] of intervals.slice(1)) {
    if (left <= end) end = Math.max(end, right);
    else {
      result.push([start, end]);
      [start, end] = [left, right];
    }
  }
  result.push([start, end]);
  return result;
}

def merge_intervals(values):
    if not values:
        return []
    intervals = sorted((a, b) for a, b in values)
    result = []
    start, end = intervals[0]
    for left, right in intervals[1:]:
        if left <= end:
            end = max(end, right)
        else:
            result.append([start, end])
            start, end = left, right
    result.append([start, end])
    return result

示例假设每个输入都满足左端点不大于右端点，数值可比较。真实接口需要先校验输入，不要让算法默默解释错误区间。

闭区间与半开区间，边界不同

闭区间 [1, 2] 包含 2，[2, 3] 也包含 2，因此按重叠合并规则会合并。

半开区间 [1, 2) 不包含 2，与 [2, 3) 没有交集。若系统只合并实际重叠区间，判断应使用严格小于；若为了表示连续覆盖而允许合并相接区间，则可以采用另一条明确约定。

日历、字节范围和时间窗口经常采用不同端点形式。不能把一个题目的小于等于条件直接复制到所有业务。

用不变条件解释正确性

扫描过程中，result 中的区间已经确定且彼此不重叠；start、end 覆盖当前这一组能够连接的区间。

新出现的区间只有两种情况：能连接，就扩大当前范围；不能连接，就把当前范围定稿，再建立下一组。最后循环结束，仍有一组当前区间，需要追加。

漏掉最后一次追加，会让最后一组结果消失。这也是很常见的实现错误。

排序主导时间 O(n log n)，扫描 O(n)。本实现复制并保存排序输入，还有结果存储，所以不能宣称额外空间为零。验证应包括空输入、单区间、完全包含、相接、乱序和重复区间。

面试官继续追问

已经有序，还需要再排序吗？

如果接口保证并且能验证按左端点有序，可以直接扫描，把这部分时间降到 O(n)。不能只根据一个样本看起来有序就省略。

为什么不按右端点排序？

按左端点更直接保证后续不会出现更早起点，适合这里的合并不变条件。其他问题，例如区间选择，可能采用右端点策略，但目标不同。

如何合并流式到来的无序区间？

不能直接沿用一次顺序扫描，需要缓存、重新排序或维护有序结构。是否能够立即输出最终结果，取决于有没有后续更早区间的保证。

面试速记卡

• 排序依据：左端点递增，后续不会突然出现更早起点。
• 合并条件：按端点约定判断是否重叠或相接。
• 右端点更新：取最大值，不被包含区间缩短。
• 循环边界：扫描结束要保存最后一组。
• 复杂度：排序 O(n log n)，扫描 O(n)，存储另算。