合并区间

Timeline Sweeper · 时间轴清障车

把重叠的时间段 / 路段合成一整段

一句话核心：先按左端点排序，再从左到右扫描，只和结果里的最后一个区间 last 比较。

经典输入

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

排序传送带 → 扫描 cur → 结果仓库 res

区间合并不是「两两比对所有区间」，而是排序后维护一个已合并、互不重叠的结果列表。当前区间只需要和最右边的 last 接触——接不上就说明和前面更早的区间更接不上。

案例切换经典四段输入，演示排序、重叠合并与 gap 追加。

速度Step 1/11 · 题目输入

题目输入：合并所有重叠区间

当前 cur: —
结果尾 last: —
当前 res: []

每条区间表示道路上的一段封闭施工路段。目标是把所有重叠（或相接）的路段合成连续封闭区间。

输入 intervals = [[1,3], [2,6], [8,10], [15,18]]。只要两段在数轴上有交集或端点相接，就要融合成一段。

时间轴道路 · 清障合并区

刻度 0 – 20

[1,3]

[2,6]

[8,10]

[15,18]

原始区间卡片

[1, 3]

[2, 6]

[8, 10]

[15, 18]

结果仓库 res · 合并完成区

[] 空仓库，等待第一段封闭区间

TypeScript · 逐行高亮

merge(intervals)

1function merge(intervals: number[][]): number[][] {
2  intervals.sort((a, b) => a[0] - b[0])
3  const res: number[][] = []
4 
5  for (const cur of intervals) {
6    if (res.length === 0) {
7      res.push([...cur])
8      continue
9    }
10    const last = res[res.length - 1]
11    if (cur[0] <= last[1]) {
12      last[1] = Math.max(last[1], cur[1])
13    } else {
14      res.push([...cur])
15    }
16  }
17  return res
18}

不变量

处理完前 i 个区间后，res 中保存的是这些区间合并后的结果；res 内部从左到右排列，并且互不重叠。

当前步仍成立：尚未开始处理，不变量待建立。

复杂度说明

总时间 O(n log n)：排序主导；排序后的线性扫描是 O(n)。
空间：不计输出数组时额外 O(1)；若计入结果数组 res 则为 O(n)。

步骤轨迹

#	阶段	说明	res
1	题目输入	题目输入：合并所有重叠区间	0
2	为什么排序	为什么必须先排序？	0
3	排序完成	按左端点排序完成	0
4	首段入仓	第一个区间直接入仓	1
5	比较 cur/last	比较 cur 与 last	1
6	重叠融合	重叠：磁吸融合	1
7	比较 cur/last	比较 cur 与 last	1
8	断开追加	断开：出现 gap，追加新区间	2
9	比较 cur/last	比较 cur 与 last	2
10	断开追加	断开：出现 gap，追加新区间	3
11	最终答案	扫描完成 · 最终答案	3

面试回答模板

先把区间按左端点排序，时间 O(n log n)。然后从左到右扫描，维护结果列表 res。因为 res 内部互不重叠，当前区间 cur 只需要和最后一个 last 比较：若 cur.start <= last.end 就合并，更新 last.end = max(last.end, cur.end)；否则把 cur 作为新区间 append。扫描是 O(n)，额外空间不计输出时为 O(1)，计结果数组为 O(n)。