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

怎样从“intervals=[[1,2],[3,5],[6,7]]，插入 [2,4]，输出 [[1,5],[6,7]]。”推导出 区间 · 三段扫描，并证明每次状态变化都不会漏掉答案？

中心结论：intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。

这一题是第 56 题的加强版。给出多个没有重叠的区间，然后再给一个区间，要求把如果有重叠的区间进行合并。

在本站主例中，intervals=[[1,2],[3,5],[6,7]]，插入 [2,4]，输出 [[1,5],[6,7]]。

算法最终需要得到或观察：[[1,5],[6,7]]。

两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“区间时间轴”，明确答案需要观察什么。
2. 2状态只维护 i、current interval、newStart、newEnd、result、phase（左/融/右）。
3. 3转移每一步按照 intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。
4. 4收尾读取 [[1,5],[6,7]]。，并复核边界与复杂度。

排序把二维的任意关系压缩成从左到右的一次扫描。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：i、current interval、newStart、newEnd、result、phase（左/融/右）。

可以分 3 段处理，先添加原来的区间，即在给的 newInterval 之前的区间。然后添加 newInterval ，注意这里可能需要合并多个区间。最后把原来剩下的部分添加到最终结果中即可。

intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。

执行过程中持续维护：i、current interval、newStart、newEnd、result、phase（左/融/右）。

正确性依赖以下不变量：result 中是已确定的左侧安全区间；newInterval 是当前融合区；右侧区间尚未处理。

面试时可以压缩为：因为 intervals 已排序且互不重叠，先 copy 左侧、再 merge 重叠、最后 append 右侧，一次扫描 O(n)。

落到当前题，执行机制可以压缩为：intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入intervals=[[1,2],[3,5],[6,7]]，插入 [2,4]，输出 [[1,5],[6,7]]。 因为：intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。
2. 2定位新区间插入位置先放入所有 end < new.start 的区间。 因为：这些区间与新区间不相交,顺序不变。
3. 3前段区间已就位左侧完全不相交的区间直接保留。 因为：start 有序时,end < new.start 意味着完全在左侧。
4. 4与 [1,2] 重叠,扩展合并段把重叠区间并入 merged。 因为：连续重叠区间应合成一段。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6与 [3,5] 重叠,扩展合并段把重叠区间并入 merged。 因为：连续重叠区间应合成一段。
7. 7插入并合并完成新区间与重叠段合并,再接上右侧剩余段。 因为：一次线性扫描,O(n)。
8. 8收尾与复杂度[[1,5],[6,7]]。 因为：时间 O(n) · 空间 O(n)。intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// Interval define
type Interval = structures.Interval

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */

func insert(intervals []Interval, newInterval Interval) []Interval {
	res := make([]Interval, 0)
	if len(intervals) == 0 {
		res = append(res, newInterval)
		return res
	}
	curIndex := 0
	for curIndex < len(intervals) && intervals[curIndex].End < newInterval.Start {
		res = append(res, intervals[curIndex])
		curIndex++
	}

	for curIndex < len(intervals) && intervals[curIndex].Start <= newInterval.End {
		newInterval = Interval{Start: min(newInterval.Start, intervals[curIndex].Start), End: max(newInterval.End, intervals[curIndex].End)}
		curIndex++
	}
	res = append(res, newInterval)

	for curIndex < len(intervals) {
		res = append(res, intervals[curIndex])
		curIndex++
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
    // 1. 主例
    //    输入：mode="insert-interval", intervals=[[1,2],[3,5],[6,7]], newInterval=[2,4]
    //    期望：[[1,5],[6,7]]。
    //
    // 2. 失败 / 未命中
    //    检查：边界相等要用 start <= newEnd；不要忽略 append newInterval；空 intervals 直接返回 newInterval。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC56 合并区间；LC435 无重叠区间；LC252 会议室
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意intervals=[[1,2],[3,5],[6,7]]，插入 [2,4]，输出 [[1,5],[6,7]]。
2. 2重复两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。
3. 3优化intervals 已排序且互不重叠，一次 O(n) 扫描：左侧 copy、重叠融合 newInterval、右侧 append。
4. 4证明result 中是已确定的左侧安全区间；newInterval 是当前融合区；右侧区间尚未处理。
5. 5复杂度时间 O(n)，空间 O(n)