插入区间：让新区间穿过时间轴，撞到就合并

Road Crew · 道路维修队

不是重新排序，而是利用已排序区间，把扫描过程拆成：左侧安全区、重叠融合区、右侧剩余区。

intervals

[[1,2],[3,5],[6,7]]

newInterval

[2,4]

→

output

[[1,5],[6,7]]

O(n) 时间O(n) 输出空间

蓝色 = 已有封锁段 · 橙色 = 施工区 newInterval · 绿色 = 已进入 result

LC57 的核心不是「把 newInterval 加入列表再排序 merge」——那样能做，但忽略了 intervals 已经有序这一前提。正确做法是：橙色施工区沿时间轴从左扫到右，左侧直接 copy，碰到就融合扩张，融合结束后写入 result，再把右侧剩余区间一次性 append。

案例切换[[1,2],[3,5],[6,7]] 插入 [2,4]：边界接触 + 连续融合，输出 [[1,5],[6,7]]。

Step 1/11 · 建立世界 · Frame 1 · 建立世界：已有封锁段 + 橙色施工区

道路时间轴 · 封锁段扫描

刻度 0 – 10

[1,2]

[3,5]

[6,7]

newInterval[2,4]

已有区间 intervals（蓝色 · 已排序）

[1, 2]

[3, 5]

[6, 7]

new [2, 4]

result 队列（绿色 · 已确定）

[] 等待左侧安全区或融合结果

Go · 逐行高亮

insert(intervals, newInterval)

1func insert(intervals [][]int, newInterval []int) [][]int {
2    res := make([][]int, 0, len(intervals)+1)
3    i := 0
4    n := len(intervals)
5 
6    for i < n && intervals[i][1] < newInterval[0] {
7        res = append(res, intervals[i])
8        i++
9    }
10 
11    for i < n && intervals[i][0] <= newInterval[1] {
12        if intervals[i][0] < newInterval[0] {
13            newInterval[0] = intervals[i][0]
14        }
15        if intervals[i][1] > newInterval[1] {
16            newInterval[1] = intervals[i][1]
17        }
18        i++
19    }
20 
21    res = append(res, newInterval)
22 
23    for i < n {
24        res = append(res, intervals[i])
25        i++
26    }
27 
28    return res
29}

机器状态面板

i（扫描位置）: —
current interval: —
newStart: 2
newEnd: 4
result: []
phase: —

城市道路已有若干蓝色封锁段（intervals 已按 start 排序、互不重叠）。维修队要在时间轴上插入一段橙色施工封锁区 newInterval。

intervals = [[1,2], [3,5], [6,7]]，newInterval = [2,4]。目标输出 [[1,5], [6,7]]。关键：不需要重新排序，只需一次从左到右扫描。

为什么正确

因为 intervals 原本已经按 start 升序排列，并且互不重叠，所以每个区间相对 newInterval 只可能属于三类：① 在 newInterval 左边（end < newStart）；② 和 newInterval 重叠（start <= newEnd）；③ 在 newInterval 右边（start > newEnd）。扫描过程中，左侧区间一旦进入 result，后面不会再影响它；重叠区间被持续吸收到 newInterval 中；一旦遇到右侧区间，说明后面所有区间都在右侧，可以直接追加。

不变量：扫描过程中，result 里保存的是「已确定不会再变」的左侧安全区间；newInterval 是当前正在扩张的融合区；尚未扫描的区间都在右侧。

常见误区

边界相等时不合并：错误写法 start < newEnd；正确是 start <= newEnd，端点接触也算重叠。
忽略 intervals 已经有序，把 newInterval 加入后再排序 merge——能做，但没有体现 LC57 的 O(n) 核心。
重叠循环结束后忘记 append newInterval，导致融合结果丢失。
空数组 intervals = [] 时，答案就是 [newInterval]，两个 while 都不进，直接 push。
newInterval 完全在左或完全在右时，要正确处理：左侧全 copy、中间零合并、或右侧全 append。

面试回答

因为 intervals 已排序且互不重叠，所以我先加入所有在新区间左边的区间，再合并所有重叠区间，最后追加右边剩余区间。整个过程只扫描一次，时间 O(n)，输出空间 O(n)。

迁移练习

→LC56 合并区间 — 无序输入需先排序，再维护 res 尾部 last
→LC435 无重叠区间 — 判断重叠的变体：最多保留几段
→LC252 会议室 — 判断 intervals 是否有交集

复杂度

时间 O(n)：三个 while 共用指针 i，每个区间最多访问一次。
空间 O(n)：输出 result 数组；不计输出时额外 O(1)。

步骤轨迹

#	阶段	说明	newInterval
1	建立世界	Frame 1 · 建立世界：已有封锁段 + 橙色施工区	[2,4]
2	左侧判断	左侧判断 · 扫描 [1,2]	[2,4]
3	重叠判断	重叠判断 · 扫描 [1,2]	[2,4]
4	融合吸收	融合吸收 · [1,2] 被橙色磁场吸收	[1,4]
5	左侧判断	左侧判断 · 扫描 [3,5]	[1,4]
6	重叠判断	重叠判断 · 扫描 [3,5]	[1,4]
7	融合吸收	融合吸收 · [3,5] 被橙色磁场吸收	[1,5]
8	重叠结束	重叠结束 · 扫描 [6,7]	[1,5]
9	写入结果	写入融合结果 · newInterval 进入 result	[1,5]
10	右侧追加	右侧追加 · [6,7]	[1,5]
11	最终答案	Frame 8 · 最终答案：只扫一遍，没有重新排序	[1,5]