题目重点：两组按起点排序的区间可能各自重叠，输出其并集的互不重叠区间。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 采用闭区间[a,b]且a<=b，端点相同算相交；两个输入都按起点非降排序。输出新列表，不改输入。
- 若未排序，先排序全部区间再扫描；不能沿用线性归并复杂度。半开区间是否合并相接区间需明确输出规范。
- 无序单列表变体同样采用闭区间并集；先复制并排序，保持调用者输入不变。
解题路线
- 两个指针选择起点更小的下一个区间，相当于合并排序的merge步骤，确保处理顺序仍按起点排列。
- 结果最后一个区间是已处理输入最右侧连通块；若新start<=lastEnd，扩大end为max；否则结束旧块并开始新块。
- 各输入内部是否重叠不影响算法，统一在输出处合并。闭区间接触也属于同一连通块；不要用严格<遗漏[a,b]与[b,c]。
- 无序单列表先按(start,end)排序，再复用有序归并逻辑。反例[[8,9],[1,4],[2,6]]说明必须先建立起点顺序；否则后到左侧区间无法仅靠尾块合并。排序后未来start不小于当前start，结束的左侧连通块不会再被连接。
手动走一遍
第一组[[1,4],[8,9]]，第二组[[2,6],[6,7]]，结果[[1,7],[8,9]]。包含区间[2,3]不会把[1,7]的终点缩回3。 无序输入[[8,9],[1,4],[2,6]]返回[[1,6],[8,9]]；输入顺序保持不变。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def merge_sorted_intervals(first, second):
"""Closed intervals; each input sorted by start; overlapping inputs allowed."""
for rows in (first, second):
if any(a > b for a, b in rows):
raise ValueError("reversed interval")
if any(rows[i][0] > rows[i + 1][0] for i in range(len(rows) - 1)):
raise ValueError("inputs must be start-sorted")
i = j = 0
answer = []
while i < len(first) or j < len(second):
if j == len(second) or (i < len(first) and first[i][0] <= second[j][0]):
start, end = first[i]; i += 1
else:
start, end = second[j]; j += 1
if answer and start <= answer[-1][1]:
answer[-1][1] = max(answer[-1][1], end)
else:
answer.append([start, end])
return answer
def merge_unsorted_intervals(intervals):
"""Closed interval union, arbitrary input order, preserves caller input."""
ordered=sorted((a,b) for a,b in intervals)
return merge_sorted_intervals(ordered, [])
复杂度
O(m+n)时间，O(1)辅助状态，输出O(m+n)；代码额外做一次合法性检查仍线性。 无序单列表N条需O(N log N)排序、O(N)复制/排序空间和输出，不能沿用两组已排序输入的线性复杂度。
易错点与追问
容易失分的边界
- 把end直接赋新end会在包含区间上错误缩短；必须max。
- 单个列表已排序不代表内部无重叠，不能省略最后结果合并步骤。
继续深挖
- k组有序区间用最小堆归并，O(N log k)，再用同一个并集合并逻辑。
- 若要找到最大重叠人数而不是并集，需要端点事件计数和明确同刻进出顺序，输出目标不同。
