LeetCode 1288 Remove Covered Intervals：区间覆盖判定与两种排序贪心策略详解

LeetCode 1288 Remove Covered Intervals：区间覆盖判定与两种排序贪心策略详解

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇围绕 LeetCode 1288「移除被覆盖区间（Remove Covered Intervals）」展开，基于本仓库文档 articles/remove-covered-intervals.md 的完整解法脉络，从暴力枚举讲到两种排序贪心，并对照仓库中 Python 实现、C 实现 与 Kotlin 双版本实现 的源码细节。读完本篇，你将掌握「区间覆盖（containment）」与「区间重叠（overlap）」的本质区别、按起点升序 + 终点降序这一关键排序规则的原理，以及如何用单遍扫描配合prevL/prevR或「历史最大右端点」两种状态变量在 O(n log n) 时间内解决问题。

问题定义与前置知识

给定数组intervals，其中intervals[i] = [li, ri]表示区间[li, ri)，要求移除所有被列表中其他区间完全覆盖的区间，返回移除后剩余的区间数量。仓库中 C 语言题解 的文件头注释给出了与题目一致的形式化定义，并标注了期望复杂度：时间O(n log n)、空间O(1)。

按照原文档的 Prerequisites 部分，动手前应具备三方面基础：

• 排序（Sorting）：使用自定义比较器按「起点升序、终点降序」排序；
• 区间问题（Interval Problems）：理解区间包含（containment）与重叠（overlap）的概念差异；
• 贪心算法（Greedy Algorithms）：在有序序列上按序做局部最优决策。

判定一个区间i是否被区间j覆盖的充要条件是：j的起点不晚于i的起点，且j的终点不早于i的终点，即intervals[j][0] <= intervals[i][0] and intervals[j][1] >= intervals[i][1]。这个判定条件是全文所有解法的核心。

解法一：暴力枚举 O(n²)

思路

对每对区间(i, j)逐一检查是否存在覆盖关系：区间i被区间j覆盖当且仅当j起点更靠前（或相等）且终点更靠后（或相等）。统计所有"未被任何其他区间覆盖"的区间个数即为答案。

算法步骤

1. 以区间总数n作为初始计数res；
2. 对每个区间i，枚举所有其他区间j（i != j）；
3. 若存在某个j覆盖i，则res -= 1并break（一个区间只需被覆盖一次就应移除）；
4. 返回剩余计数。

class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: n = len(intervals) res = n for i in range(n): for j in range(n): if (i != j and intervals[j][0] <= intervals[i][0] and intervals[j][1] >= intervals[i][1] ): res -= 1 break return res

原文档同时给出了 Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 共八种语言的等价实现，逻辑完全一致：双重循环 +i != j判等排除自身 + 命中即break。

复杂度

• 时间复杂度：$O(n^2)$，每对区间检查一次；
• 空间复杂度：$O(1)$ 额外空间。

边界细节

判定中两处比较都使用「等于」也成立（<=与>=），因此两个完全相同的区间会互相覆盖、全部被移除——这与题目"被另一个区间覆盖"的语义一致。而i != j条件保证区间不会因"自己覆盖自己"而被误删。这两个细节是暴力解法正确性的关键。

解法二：排序贪心 I（起点升序 + 终点降序）

思路

排序能让"覆盖者"总是先于"被覆盖者"出现。关键规则是：按起点升序，起点相同时按终点降序。这样同起点的区间中，最长的一定排在最前面；于是扫描时只需追踪"上一个保留区间"的边界prevL/prevR，若当前区间满足prevL <= l and prevR >= r，说明它被前面某个保留区间覆盖，直接跳过；否则保留并更新边界。

算法步骤

1. 按起点升序、终点降序排序；
2. 用prevL, prevR记录上一个被保留区间的边界（初始为排序后第一个区间）；
3. 遍历每个区间，若prevL <= l and prevR >= r则跳过（被覆盖）；
4. 否则计入res，并把prevL, prevR更新为当前区间；
5. 返回res。

class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: (x[0], -x[1])) res = 1 prevL, prevR = intervals[0][0], intervals[0][1] for l, r in intervals: if prevL <= l and prevR >= r: continue res += 1 prevL, prevR = l, r return res

各语言的比较器写法（原文档均完整给出）在语义上等价于 C++ 的a[0] == b[0] ? b[1] < a[1] : a[0] < b[0]与 Java 的a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0])。

复杂度

• 时间复杂度：$O(n \log n)$，由排序主导；
• 空间复杂度：$O(1)$ 或 $O(n)$，取决于所用排序算法的实现。

仓库源码印证

仓库中的 python/1288-remove-covered-intervals.py 采用了同一排序规则，但换了一种等价的状态维护方式：

# sort on the basis of inc li first and then on the basis of dec length (=> -ri) intervals.sort(key=lambda x: (x[0], -x[1])) covered, maxri = 0, 0 for _, ri in intervals: if ri > maxri: maxri = ri else: covered += 1 return len(intervals) - covered

从源码结构看，它不再单独维护prevL，而是只用一个maxri（已见区间的最大右端点）：由于排序保证当前区间起点不小于所有前面区间的起点，所以「右端点不大于历史最大右端点」即等价于「被覆盖」。而 kotlin/1288-remove-covered-intervals.kt 则在同一文件中给出了两个版本——先是用LinkedList保存保留下来的区间（时间O(n log n)、空间O(n)，通过peekLast()取"上一个保留区间"做覆盖判定），随后附上注释标注的O(1)空间优化版，即只保存prev指针变量的写法，与文档解法二完全对应。

C 语言实现中的比较器

c/1288-remove-covered-intervals.c 用qsort实现了同样的排序规则，值得注意其比较函数的写法：

int cmp_fun(const void *const_a, const void *const_b) { const int* interval_a = *(const int **)const_a; const int* interval_b = *(const int **)const_b; if (interval_a[0] == interval_b[0]) return interval_b[1] - interval_a[1]; else return interval_a[0] - interval_b[0]; }

该文件头部的注释把排序偏序关系写得很精确：a <= b ⇔ (a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]))。其扫描阶段则维护end（已保留区间中的最大右端点），若intervals[i][1] <= end说明当前区间起点不小于前面、右端点不大于历史最大，直接判为被覆盖并递减number_remaining；否则更新end。

解法三：排序贪心 II（仅按起点排序 + 历史最大右端点）

思路

如果不想写"终点降序"这种稍显特殊的比较器，可以只按起点升序排序，同时追踪"当前主导区间"的起点和历史最大右端点end。当前区间被保留的条件变为两个严格不等式同时成立：起点严格大于记录的start，且右端点严格大于已知的最大end；任何时刻都要用max(end, r)刷新最大右端点。

算法步骤

1. 仅按起点升序排序；
2. 维护start（当前主导区间起点）与end（历史最大右端点），初始为第一个区间；
3. 若start < l and end < r同时成立，说明当前区间是新的一段覆盖，更新start = l并res += 1；
4. 无论是否计数，都要执行end = max(end, r)；
5. 返回res。

class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: intervals.sort() res, start, end = 1, intervals[0][0], intervals[0][1] for l, r in intervals: if start < l and end < r: start = l res += 1 end = max(end, r) return res

两种严格不等式的含义

这里与解法二的非严格比较（<=/>=）形成对照，理解其原因是深入本题的关键：

• end < r（严格）：右端点必须严格超出历史最大才算新贡献。若r == end，当前区间右端点被历史区间端点覆盖——由于排序后历史区间起点不晚于当前起点，r == end意味着当前区间被覆盖（例如[1,3]之后出现[1,3]或[2,3]）。
• start < l（严格）：起点必须严格大于记录的主导起点。若l == start且r > end，说明当前区间与主导区间同起点但更长，此时当前区间反过来覆盖了之前的主导区间，start = l保持不变即可，但不应重复计数——同起点下最长者唯一，此前计数的正是它。
• 更新start只在计入新区间时执行，且由于排序保证l >= start，start = l实际上是"确认这个同起点组的最长代表"。

这一套推理解释了为什么同一排序下，比较算子从严变成松（解法二的prevL <= l）与保持严格（本解法的start < l）都能正确，但依赖的状态变量完全不同。

复杂度

• 时间复杂度：$O(n \log n)$；
• 空间复杂度：$O(1)$ 或 $O(n)$，取决于排序算法。

常见错误（Common Pitfalls）

原文档在结尾归纳了三类高频错误，逐条拆解如下：

1. 排序顺序写错

最容易犯的错误是只按起点排序而不处理终点。当两个区间起点相同时，更长的必须排在前面（终点降序），否则会出现把长区间误判为被短区间覆盖的情况。例如[1,4]与[1,2]起点相同：若排序后[1,2]在前，prevL/prevR会先记录[1,2]，随后[1,4]因右端点更大而保留并更新边界——看似正确，但若后续还有[1,3]，它会被已更新的[1,4]正确判为覆盖；真正的错误场景在于短区间在前时，长区间被跳过判定逻辑干扰（prevR >= r不成立才保留），核心问题是"同起点最长者优先"这一不变式被破坏后，"只看上一个保留区间"的策略不再安全。解法二用"起点升序 + 终点降序"排序显式保证该不变式，解法三则用"历史最大end"规避了对同起点顺序的依赖。

2. 把"覆盖"与"重叠"混淆

区间被覆盖要求完全包含：start <= start AND end >= end。常见错误是只检查区间是否有交叠（overlap）。例如[1,4]覆盖[2,3]需要1 <= 2 and 4 >= 3同时成立；而[1,3]与[2,4]只是部分重叠，二者互不覆盖，都不能被移除。

3. 返回值弄反（off-by-one 类错误）

题目要求的是剩余区间数，而不是被移除的区间数。若统计出k个被覆盖区间，应返回n - k而非k。仓库 Python 实现 正是"先数 covered、最后len(intervals) - covered"的写法，C 实现 则是"从intervalsSize起逐个递减"，两者都是对这一坑的显式防御。

两种贪心策略对比与选型建议

选型建议：手写竞赛中解法三比较器更简单、不易写错排序细节，但严格/非严格不等式需要仔细推导（如上文同起点更长区间的反向覆盖情形）；解法二逻辑直白、与"区间合并"系列题目的状态维护方式一致，更易推广到 merge-intervals 等兄弟问题。仓库内的多语言实现（C、Kotlin、Python）恰好覆盖了这两种状态维护风格，可作为对照阅读材料。

小结

• 本题的核心是「完全包含」判定：j.start <= i.start && j.end >= i.end，判定时等号两侧都要成立，因此相同区间会互相覆盖；
• 暴力双重循环 $O(n^2)$ 可作为正确性基准；
• 两种 $O(n \log n)$ 贪心均靠排序建立"覆盖者先出现"的不变式：一种用终点降序 + 追踪上一个保留区间，一种用历史最大右端点 + 严格不等式；
• 仓库文档 articles/remove-covered-intervals.md 提供了九种语言的完整代码，配合仓库中的 C、Python、Kotlin 实现，可完整覆盖从思路推导到多语言落地的学习路径。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode