无重叠区间：最少删除多少个区间？（LeetCode 435）

简化版

给一组区间，求最少删除几个才能让剩下的区间互不重叠。等价于求「最多能保留几个互不重叠的区间」，答案 = 总数 − 最多保留数。贪心策略：按右端点升序排序，每次贪心保留「结束最早」的区间——它右端小，给后面留的空间最大。遍历时若下一个区间的左端 >= 上一个保留区间的右端，就不重叠、保留它；否则重叠，删掉（计数 +1）。

详细版

int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);   // 按右端点升序
    int end = intervals[0][1];    // 已保留区间的右端
    int count = 1;                // 已保留的区间数（第一个必留）
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {   // 不重叠：保留
            end = intervals[i][1];
            count++;
        }
        // 否则重叠：删掉当前（不更新 end）
    }
    return intervals.length - count;    // 删除数 = 总数 - 最多保留数
}

转化：「最少删除」= 总数 − 「最多不重叠保留数」。这是经典的区间调度问题（activity selection）。
按右端点排序：贪心保留结束最早的，给后续留最大空间。
保留条件：当前左端 >= 上一保留区间右端（相接 == 不算重叠，可保留）。
复杂度：排序 O(n log n) 主导。

完整版教学

一、换个角度：求「最多保留」而非「最少删除」

直接想「删哪些」很乱，转化一下：要让剩下的互不重叠，就是从所有区间里挑出一个「两两不重叠」的最大子集。挑出的越多，删的就越少。于是：

最少删除数 = 总区间数 − 最多能保留的不重叠区间数

这个「最多不重叠区间数」正是算法导论里的区间调度 / 活动选择问题，有经典贪心解。

二、为什么按右端点排序、选结束最早的

贪心核心：每次都保留「结束时间最早」的区间。直觉——一个区间结束得越早，它占用的「时间轴」越靠左、越短，给后面的区间留出的空间就越大，从而能容纳更多后续区间。

所以按右端点升序排序，从左到右贪心地挑：维护上一个已保留区间的右端 end，遇到新区间：

当前左端 >= end：和上一个不重叠 → 保留它，更新 end 为它的右端。
当前左端 < end：重叠 → 必须删掉一个。因为我们保留的是「结束更早」的那个（对后续更友好），所以删当前这个，end 不变。

三、贪心正确性（交换论证）

为什么「选结束最早」一定得到最多保留数？用交换论证：设最优解的第一个区间是 X，而贪心选的是结束最早的 A。因为 A 结束最早，A.end <= X.end。把最优解里的 X 换成 A：由于 A 结束更早，它不会和最优解中 X 之后的任何区间冲突（那些区间都在 X.end 之后开始，更在 A.end 之后）。所以换成 A 后区间数不变、仍合法。以此类推，贪心的每一步选择都能「掰」进某个最优解，故贪心保留数 = 最多保留数。

四、按右端点 vs 按左端点

本题（选最多不重叠）必须按右端点排。若按左端点排贪心选结束最早，会出错——因为左端小不代表结束早，一个左端很小但拖得很长的区间会挤掉很多短区间。
对比合并区间 56 按左端点排：目的不同（56 要合并所有重叠，本题要保留最多不重叠），所以排序键相反。这是区间题的核心分水岭：合并看左端点，贪心选择看右端点。

五、端点相接与变体

相接不算重叠：[1,2] 和 [2,3] 不冲突，可都保留。所以保留条件用 >=（当前左端 >= end）。若某题规定「相接也算重叠」，改成 >。
**变体：用最少数量的箭引爆气球（452）**几乎同一个模型（求「最多不重叠组」= 最少箭数），只是相接算重叠、且直接求箭数不用做减法。两题一起记。
**变体：会议室 II（253）**问「最多同时重叠数」，那是扫描线，不是这个贪心——别混。

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

本题扫描成立的结构是：最少删除 = 总数 - 最多保留；按右端升序选择最早结束且与上次不重叠的区间。

任何最优解的第一个区间可换成结束更早者，不减少后续可选区间

数字推演：[1,2],[2,3],[3,4],[1,3] 可保留前三段，删1段。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：端点相接通常不重叠；相同右端次序不影响数量；空数组结果0。

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

七、方法对比与专项测试

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

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

正确性复核要落到本题的排除逻辑：最少删除 = 总数 - 最多保留；按右端升序选择最早结束且与上次不重叠的区间。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

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

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

工程上还要单独确认：端点相接通常不重叠；相同右端次序不影响数量；空数组结果0。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：应优先保留最长区间。 长区间往往占用更多后续空间。
误区：按左端最早选一定最优。 经典证明依赖最早结束。
误区：最少删除要直接模拟删除。 转成最大保留更容易证明。
追问：交换论证如何做？ 把最优解首段换成更早结束段，后续仍可行。
追问：端点相接算重叠吗？ 本题通常不算，即 start≥end 可选。
追问：复杂度是多少？ 排序 O(n log n)，扫描 O(n)。

九、加强记忆

无重叠区间（最少删除）= 区间调度贪心。转化：最少删除 = 总数 − 最多不重叠保留数。做法：按右端点升序排序，贪心保留「结束最早」的（右端小给后面留空间最大），当前左端 >= 上一保留右端 就保留并更新 end，否则删掉。正确性靠交换论证。牢记按右端点排（对比合并区间按左端点）、相接不算重叠用 >=。孪生题射气球 452 同模型。O(n log n)。

简化版

详细版