题干与适用场景
给定一组无序闭区间 intervals，每个元素为 [start, end]，且 start <= end。请合并所有重叠区间，返回一个按起点升序排列、两两不重叠的新列表，并保持覆盖范围不变。本题使用闭区间语义，所以 [1, 4] 与 [4, 5] 共享点 4，应合并为 [1, 5]。函数不得修改输入。
例如：
输入：[[8, 10], [1, 3], [2, 6], [15, 18]]
输出：[[1, 6], [8, 10], [15, 18]]输入可以为空，也可能包含重复区间、负数端点、零长度区间和完全嵌套的区间。基础题假设每个元素都恰好有两个合法整数，不在合并函数里处理格式错误。它适用于通用软件工程编码面试，核心能力是把任意顺序转化为可局部决策的顺序，再证明这个贪心决策不会漏掉跨区间的合并。
面试官考察点
第一项信号是候选人会不会先定义区间语义。闭区间、半开区间以及“相邻也算可合并”会直接改变判断条件。只写 start < current_end 而不说明语义，在共享端点用例上可能答错。
第二项信号是能否解释排序为什么有用。排序后，下一个区间的起点不会小于当前起点；如果它已经大于当前合并区间的终点，那么所有更晚区间的起点只会更大，当前区间可以安全输出。强回答会给出这个“可以定稿”的依据，而不只说“排序后扫一遍”。
第三项信号是嵌套区间处理。合并 [1, 10] 与 [2, 3] 时，终点必须取 max(10, 3)；直接覆盖成 3 会丢失覆盖范围。链式重叠也必须与正在扩张的合并结果比较，而不是只比较相邻原始区间。
最后还会检查代码契约、复杂度和验证方式。排序通常决定 O(n log n) 时间；本实现用新排序列表和新结果列表换取输入不可变，总空间为 O(n)。测试不能只覆盖标准示例，还要验证输入没有被修改、输出已排序且两两不重叠，并用慢速基准实现做随机差分。
回答前需要澄清的问题
- 区间是闭区间还是半开区间？共享端点是否合并？ 本题是闭区间，所以条件为
nextstart <= currentend。如果业务把相邻区间视为分开，条件改为严格小于；半开区间[a, b)还要单独确认“连续但不重叠”是否需要合并。 - 输入是否已经按起点排序？ 已排序时可以直接线性扫描，时间降为
O(n)；无序输入需要排序或使用依赖端点范围的特殊方法。 - 允许修改输入吗？ 允许时可以原地排序并用写指针压缩结果；不允许时必须复制或使用返回新列表的排序函数。
- 端点取值范围是否很小且为整数？ 任意可比较数值使用比较排序最直接；若坐标只来自很小的整数域，可以考虑桶或差分数组，但空间会依赖坐标范围而不是区间数。
- 只做一次离线合并，还是区间持续到达？ 按起点有序的流可以边读边输出；任意顺序的流无法安全提前定稿，因为未来可能出现一个更早、更长的区间连接已有结果。
- 输出只要边界，还是要保留区间元数据？ 只合并边界不代表标签、权限或价格也能无损合并；若每段带元数据，必须另行定义聚合规则。
30 秒回答框架
“我先确认这些是闭区间，共享端点也算重叠，而且不能修改输入。我会复制并按起点、终点升序排序，然后维护一个当前合并区间。若下一个起点小于等于当前终点，就把当前终点扩展为两者终点的最大值；否则当前区间以后不可能再与更晚区间相交，可以加入答案并开始新区间。扫描结束再加入最后一个区间。排序是 O(n log n)，扫描是 O(n)，新排序列表和输出共用 O(n) 空间。正确性来自排序后的不变量：已输出区间已经定稿，当前区间恰好覆盖尚未输出的最后一个连通分量。”
分步骤深入解答
一个直接方案是反复寻找任意一对重叠区间，合并后从头扫描，直到没有变化。它容易写成双重循环，但一次合并可能让新区间与之前看过的区间再次重叠，因此需要多轮扫描，最坏会达到 O(n²) 甚至更差。这个方案适合用作小规模测试 oracle，却不适合作为主解法。
排序把全局问题变成单向扫描。先按 (start, end) 升序排列。维护 current = [currentstart, currentend]，它表示已经处理但尚未输出的最后一个合并分量。对下一个 [start, end]：
- 若
start <= currentend，两个闭区间重叠，把currentend更新为max(current_end, end)。 - 若
start > current_end，当前区间与下一个区间之间已有空隙。由于后续起点都不小于start，以后也不可能再碰到current；先输出current，再以新区间开始。
扫描过程中维护三个不变量：
- 已输出区间按起点升序排列、两两不重叠，而且以后不会再变化。
- 已输出区间与
current的并集，恰好等于所有已处理输入区间的并集。 current是已处理区间中最后一个最大合并分量，也是唯一可能与下一个区间重叠的分量。
初始时只处理排序后的第一个区间，三项都成立。遇到重叠时，只扩展最后分量的右端点，不改变覆盖范围；遇到空隙时，排序保证任何未来起点都在 current_end 之后，因此输出是安全的。归纳到扫描结束，再输出 current，便得到覆盖范围相同且无法继续合并的结果。
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
ordered = sorted((start, end) for start, end in intervals)
merged: list[list[int]] = []
current_start, current_end = ordered[0]
for start, end in ordered[1:]:
if start <= current_end:
current_end = max(current_end, end)
else:
merged.append([current_start, current_end])
current_start, current_end = start, end
merged.append([current_start, current_end])
return mergedsorted() 构造新的排序列表，元组解包也不会改写原有子列表，因此函数满足输入不可变。比较排序为 O(n log n)，扫描为 O(n)，总时间为 O(n log n)。排序副本和最坏包含 n 个区间的输出各为线性规模，所以包含输出时空间为 O(n)。若输入已经有序，跳过排序后时间为 O(n)；若允许原地修改，可原地排序并用写指针复用输入空间，但仍要说明排序实现可能使用的栈或临时缓冲区。
验证时先覆盖空输入、单区间、完全分离、共享端点、完全嵌套、重复区间、负数端点和链式重叠。例如 [[1, 2], [2, 3], [3, 4]] 必须得到 [[1, 4]]，它能抓住只与前一个原始区间比较的错误。再保存输入深拷贝，调用后确认没有变化。最后生成小型随机区间，用“反复合并任意重叠对”的慢速算法作为 oracle；本文代码已对 10,000 组固定种子随机输入完成差分验证。
在任意数值、比较模型下，排序加扫描是清晰的通用答案。若 n 很小，反复合并方案可能更短，且性能差异没有实际意义；若输入本来有序，则线性扫描更简单；若端点是很小的有界整数域，可以用桶或差分方法换取依赖坐标范围的时间和空间。面试中应先用约束证明特殊方案值得引入。
高质量示范回答
“我会先把边界说清：输入是无序闭区间，共享端点要合并，返回新列表且不改原数据。比如 [1, 4] 和 [4, 5] 的判断必须用小于等于。
暴力做法可以不断找重叠对再重扫，但合并后的新区间可能和前面元素产生新重叠，最坏要很多轮。我会先按起点排序。随后只保留一个尚未定稿的区间；下一个起点落在它的终点以内时，用两个终点的最大值扩张，否则把它写入结果并开始下一段。
这里的关键不是相邻元素本身，而是当前所有链式重叠后的结果。排序保证一旦下一个起点超过当前终点，后面所有起点也都会超过，所以当前结果可以永久定稿。由此已输出部分始终有序且互不重叠，当前部分覆盖已处理输入的最后一个合并分量。
代码会使用 sorted() 生成副本，空输入直接返回。时间是排序的 O(n log n) 加线性扫描，空间是排序副本和输出的 O(n)。我会重点测共享端点、嵌套、重复、负数和链式重叠，再用慢速两两合并作为 oracle 做随机差分，同时断言输入没有改变。”
常见错误
- 没有定义端点语义就写
<或<=→ 共享端点用例的结果取决于契约 → 先明确闭区间、半开区间和连续区间是否合并，再选择判断条件。 - 按原始顺序扫描 → 本来重叠的区间可能相隔很远，已输出结果还会被未来区间连接 → 先按起点排序，或明确输入已排序。
- 只比较相邻原始区间 →
[1, 10]、[2, 3]、[9, 12]的第三段需要与扩张后的[1, 10]比较 → 始终比较最后一个合并结果。 - 重叠时直接写
currentend = end→ 被包含区间会缩短当前覆盖范围 → 使用max(currentend, end)。 - 漏掉最后一次追加 → 循环只在遇到空隙时输出，最后分量会消失 → 循环结束后统一追加
current。 - 空输入仍读取第一个元素 → 触发越界错误 → 排序和初始化前返回空列表。
- 承诺不修改输入却调用原地排序 → 调用方看到顺序改变，甚至子列表被复用后继续变化 → 使用
sorted()和新结果对象，或把可变行为写进契约。 - 只测固定输出 → 链式重叠、输入变异或边界条件仍可能错误 → 增加性质检查和随机差分 oracle。
- 无条件声称不能快于
O(n log n)→ 已排序输入或小整数坐标域可以避开比较排序 → 把下界限定在无序、任意可比较端点的模型内。
追问及应对
追问 1：如果共享端点不算重叠，代码怎么改？
把合并条件从 start <= currentend 改为 start < currentend。但先确认业务语义：对闭区间而言，共享端点在数学上有交集；如果产品仍要求分开，实际契约是“只合并正长度重叠”。对半开区间 [a, b)，[1, 4) 与 [4, 5) 不重叠，是否把连续段合并又是独立选择。
追问 2：输入已按起点排序，而且允许修改，怎样降低额外空间？
跳过排序，并用写指针把合并结果写回输入前缀。读指针扫描新区间；重叠时更新写位置的终点，不重叠时递增写指针并复制新区间。最后返回前缀长度或前缀视图。扫描为 O(n)，除返回结果外额外空间为 O(1)，代价是破坏原输入。
追问 3：区间按起点有序地持续到达，能否流式输出？
可以。只保留一个 current；遇到起点超过当前终点的区间时输出 current，再开始新区间，流结束时输出最后一段。工作内存为 O(1)，不含输出。若到达顺序任意，未来区间可能把两段连接起来，不能安全提前输出；需要缓冲、外部排序或维护动态区间结构。
追问 4：有一亿个区间，内存放不下怎么办？
先按起点做外部排序：每批在内存中排序并写出有序 run，再执行多路归并。归并流本身已经按起点有序，可以同时运行相同的单区间合并状态，不必先生成完整的全局排序文件。CPU 比较工作仍是 O(n log n) 量级，主要新成本是磁盘 I/O 和临时存储。
追问 5：每个区间还带有价格或权限标签，能直接合并吗？
只有边界可以按当前算法求并集。若重叠段标签不同，合并成单一标签会丢失信息。需要先定义输出是标签集合、优先级最高标签，还是把端点切成标签不变的最小分段；最后一种通常要改用扫描线事件，而不是简单返回区间并集。