删除被覆盖区间后还剩几个？（LeetCode 1288）

简化版

给一组区间，若区间 [c,d] 被另一个区间 [a,b] 完全覆盖（a <= c 且 d <= b），就删掉 [c,d]。求删除所有被覆盖区间后剩余区间的数量。做法：按左端点升序排序，左端相同时按右端点降序排序；然后遍历，维护「当前保留区间的最大右端点 end」——若当前区间右端 <= end，说明被前面某区间覆盖，删掉；否则保留并更新 end。

详细版

int removeCoveredIntervals(int[][] intervals) {
    // 左端升序；左端相同则右端降序（让"大区间"排前面，先占住 end）
    Arrays.sort(intervals, (a, b) ->
        a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    int count = 0;       // 保留的区间数
    int end = 0;         // 已保留区间中最大的右端点
    for (int[] cur : intervals) {
        if (cur[1] > end) {   // 右端超出，没被覆盖 → 保留
            count++;
            end = cur[1];
        }
        // 否则 cur[1] <= end，被前面的区间覆盖 → 删除
    }
    return count;
}

排序规则是关键：左端升序保证「覆盖者」排在「被覆盖者」前面；左端相同时右端降序，让更长的区间先出现、先占住 end。
覆盖判断简化：排序后左端已满足 a <= c，只需判右端 cur[1] <= end 即被覆盖。
复杂度：排序 O(n log n)。

完整版教学

一、覆盖的定义与判断难点

[c,d] 被 [a,b] 覆盖 ⇔ a <= c && d <= b（左端不比它大、右端不比它小，把它整个包住）。直接两两判断是 O(n²)。技巧是用排序把「左端 a <= c」这个条件自动满足，从而只剩「右端」一个维度要比较，一趟扫描解决。

二、排序规则：左端升序 + 左端相同右端降序

第一关键字：左端升序。 排序后遍历，任何「后出现」的区间，其左端都 >= 之前所有区间的左端。于是要判断当前区间是否被某个「前面的区间」覆盖，覆盖条件里的 a <= c 天然成立（前面区间左端更小或相等），只需再看右端。

第二关键字：左端相同时，右端降序。 这是易错的精髓。考虑 [1,4] 和 [1,5]：它们左端相同，[1,4] 被 [1,5] 覆盖，应删 [1,4]。若右端升序（[1,4] 在前），遍历先见 [1,4] 设 end=4，再见 [1,5]（5>4）会把它当成「没被覆盖」保留——没问题；但更麻烦的情形是判断 [1,5] 是否覆盖 [1,4] 时顺序错乱。用右端降序让 [1,5] 先出现、先把 end 顶到 5，之后 [1,4]（4 <= 5）被正确判为覆盖删除。让「更大的区间」先占住 end，是这条排序规则的用意。

三、扫描逻辑

维护 end = 已保留区间里最大的右端点。遍历每个区间 cur：

cur[1] > end：当前区间的右端超出了目前所有保留区间的最大右端 → 它没被任何前面的区间覆盖（左端已 ≥ 前面，右端又更大，不可能被包住），保留，count++，更新 end = cur[1]。
cur[1] <= end：右端没超过 end，而左端又 ≥ 前面某个把 end 顶上去的区间的左端 → 它被那个区间完全覆盖，删除。

四、为什么只比右端就够（正确性）

排序后，对当前区间 cur = [c, d]，之前一定存在一个保留区间 [a, end] 使 a <= c（左端升序）。若 d <= end，则 a <= c 且 d <= end 两条同时成立，cur 被 [a, end] 覆盖。反之若 d > end，cur 右端超出所有前驱，无人能包住它。所以**「被覆盖」被简化成一个右端比较 d <= end**——这正是排序的威力。

五、易错点

忘了「左端相同右端降序」：只写左端升序，遇到左端相同的区间会误判覆盖关系（把大区间排后面，先见小区间设小 end，大区间反被当新区间，甚至漏删小区间）。这条二级排序必须有。
把「覆盖」当成「重叠」：覆盖是「完全包含」，重叠只是「有交集」。本题删的是被完全包含的，别用重叠判断。
end 初始值：设 0（或第一个区间右端）均可，只要保证第一个区间必被保留。区间端点若可能为负，初始 end 用 Integer.MIN_VALUE 更稳。

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

本题扫描成立的结构是：按左端升序、相同左端右端降序后，扫描维护已见最大右端；end≤maxEnd 即被覆盖。

同左端长区间先出现，保证短区间能被识别覆盖；左端递增后只需比较右端

数字推演：[1,4],[3,6],[2,8] 排序为[1,4],[2,8],[3,6]，最后一段被[2,8]覆盖，剩2。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：完全相同区间按题目是否视作重复覆盖；若输入可能重复需明确计数语义。

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

七、方法对比与专项测试

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

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

正确性复核要落到本题的排除逻辑：按左端升序、相同左端右端降序后，扫描维护已见最大右端；end≤maxEnd 即被覆盖。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

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

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

工程上还要单独确认：完全相同区间按题目是否视作重复覆盖；若输入可能重复需明确计数语义。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

特别要把“覆盖”和“合并”分开：[1,4] 与 [3,6] 相交但互不覆盖，两段都应保留；只有一段的左端不晚且右端不早于另一段时，后者才可删除。

八、常见误区与追问

误区：只按左端升序即可。 左端相同时必须右端降序。
误区：维护前一个区间右端就够。 应维护所有已见区间的最大右端。
误区：相交就是覆盖。 覆盖要求一段左右端都包住另一段。
追问：为什么右端降序？ 让同左端最长段先出现并覆盖短段。
追问：重复区间怎么计数？ 需按题目定义决定保留一个还是都视作覆盖。
追问：复杂度是多少？ 排序 O(n log n)，扫描 O(n)。

九、加强记忆

删除被覆盖区间 = 排序 + 一趟扫描比右端。排序规则是灵魂：左端升序（让覆盖条件 a<=c 自动成立）+ 左端相同时右端降序（让大区间先占住 end）。遍历维护最大右端 end：cur[1] > end 保留并更新，cur[1] <= end 说明被覆盖删除。正确性：排序后「被覆盖」简化成单个右端比较 d <= end。牢记「覆盖 = 完全包含 ≠ 重叠」，二级排序不能省。O(n log n)。

简化版

详细版