插入区间如何实现？（LeetCode 57）

简化版

给一个已按左端点升序、且两两不重叠的区间列表，再给一个新区间 newInterval，把它插入并合并所有重叠区间，返回结果。因为原列表已有序，不用重新排序，一趟线性扫描即可：把区间分三类处理——完全在新区间左边的直接加入结果；与新区间重叠的不断合并进 newInterval（更新其左右端点）；完全在新区间右边的先把合并好的 newInterval 加入，再把剩余区间原样加入。

详细版

int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;
    // ① 左侧：完全在 newInterval 左边（右端 < 新区间左端），原样加入
    while (i < n && intervals[i][1] < newInterval[0]) {
        res.add(intervals[i++]);
    }
    // ② 中间：与 newInterval 重叠（左端 <= 新区间右端），合并进 newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.add(newInterval);                 // 合并后的新区间入列
    // ③ 右侧：完全在 newInterval 右边，原样加入
    while (i < n) {
        res.add(intervals[i++]);
    }
    return res.toArray(new int[res.size()][]);
}

利用已有序：原列表已按左端点排序且互不重叠，无需再排序，直接三段式扫描。
三类区间：左边不重叠 / 中间重叠 / 右边不重叠。
合并时同时更新左右端：左端取 min、右端取 max。
复杂度：O(n) 时间（只扫一遍），O(n) 输出空间。

完整版教学

一、和「合并区间」的区别：这里已经有序

插入区间 57 是合并区间 56 的「增量版」：原列表本就有序且互不重叠，只是塞进来一个新区间。因为已有序，省掉了 O(n log n) 排序，可以直接 O(n) 扫描。这正是本题的考点——利用「已有序」这个前提做线性处理，而不是无脑套 56 的排序解法。

二、把区间分成三类

以 newInterval = [s, e] 为界，原列表的每个区间必属于三类之一（因为原列表有序，这三类还是从左到右连续排列的）：

完全在左边：区间右端 < s（它整个落在新区间起点之前）→ 和新区间无交集，原样保留。
与新区间重叠：区间左端 <= e 且右端 >= s（在有序、且已排除左侧后，只需判 左端 <= e）→ 要合并。
完全在右边：区间左端 > e → 在新区间之后，原样保留。

三、三段式扫描逐类处理

第一段（左侧）：while intervals[i][1] < newInterval[0]，把所有「右端小于新区间左端」的区间直接加入结果。它们和新区间没关系。

第二段（重叠）：while intervals[i][0] <= newInterval[1]，凡是「左端不超过新区间右端」的都与之重叠，不断把它们吞进 newInterval——newInterval[0] = min(...)、newInterval[1] = max(...)。注意新区间会越合并越大，右端 newInterval[1] 变大后可能又吃掉后面更多区间，循环条件 intervals[i][0] <= newInterval[1] 自动处理了这种链式合并。合并完把这个「长大了的」newInterval 加入结果。

第三段（右侧）：剩下的区间左端都 > 新区间右端，原样加入。

四、为什么合并要同时更新左右端

新区间可能既向左延伸、也向右延伸。比如原列表有 [2,3]，新区间 [1,5]，合并后左端仍取 min(1,2)=1；又如原有 [4,8]，新区间 [1,5]，右端取 max(5,8)=8。所以合并时左端 min、右端 max 都要更新，才能把新区间和所有重叠区间的最大跨度都涵盖。

五、边界与陷阱

新区间在最前/最后：若 newInterval 比所有区间都靠左，第一、二段都不执行，直接第三段把它加最前；反之全在右边，第一段吃完所有，最后加它。代码天然覆盖，不用特判。
端点相接：LeetCode 57 认为相接（如 [1,3] 和 [3,5]）算重叠要合并，所以左侧判断用 intervals[i][1] < newInterval[0]（严格小于才算不重叠）、重叠判断用 intervals[i][0] <= newInterval[1]（小于等于算重叠）。< 与 <= 别写反。
空列表：intervals 为空时，三段都跳过，只加 newInterval，正确。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：原列表已按左端排序且互不重叠，可分为完全在新区间左侧、与其相交、完全在右侧三段。

相交时同时令 newL=min、newR=max；扫描越过相交段后只插入一次

数字推演：[1,2],[3,5],[6,7] 插 [4,8] 后吸收 [3,5],[6,7] 得 [1,2],[3,8]。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：新区间可能覆盖全部、位于最前/最后；不要修改输入对象导致调用方副作用。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：原列表已按左端排序且互不重叠，可分为完全在新区间左侧、与其相交、完全在右侧三段。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“[1,2],[3,5],[6,7] 插 [4,8] 后吸收 [3,5],[6,7] 得 [1,2],[3,8]”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：新区间可能覆盖全部、位于最前/最后；不要修改输入对象导致调用方副作用。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：可以把新区间加入后无脑重排。 能做但浪费已知有序条件，标准解线性。
误区：合并只更新右端。 新区间可能向左覆盖，左右都取 min/max。
误区：新区间应在第一次重叠前输出。 要先吸收整个连续重叠段。
追问：为什么只有三段？ 原列表有序且不重叠。
追问：完全无重叠怎么办？ 在左右段交界处插入一次。
追问：复杂度是多少？ 单次扫描 O(n)，输出空间 O(n)。

九、加强记忆

插入区间 = 利用已有序，三段式 O(n) 扫描（省去排序）。把原区间按位置分三类：右端 < 新左端 的原样加（左侧）→ 左端 <= 新右端 的合并进 newInterval（中间，左 min 右 max，链式吞并）→ 加入合并后的 newInterval → 剩余原样加（右侧）。合并要同时更新左右端；< 与 <= 决定端点相接算不算重叠（57 算，故左侧用 <、重叠用 <=）。核心：别排序、分三段、合并时左 min 右 max。

简化版

详细版