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起点更靠前或相等且终点更靠后或相等。统计所有未被任何其他区间覆盖的区间个数即为答案。算法步骤以区间总数n作为初始计数res对每个区间i枚举所有其他区间ji ! j若存在某个j覆盖i则res - 1并break一个区间只需被覆盖一次就应移除返回剩余计数。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说明它被前面某个保留区间覆盖直接跳过否则保留并更新边界。算法步骤按起点升序、终点降序排序用prevL, prevR记录上一个被保留区间的边界初始为排序后第一个区间遍历每个区间若prevL l and prevR r则跳过被覆盖否则计入res并把prevL, prevR更新为当前区间返回res。class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) - int: intervals.sort(keylambda 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(keylambda 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)刷新最大右端点。算法步骤仅按起点升序排序维护start当前主导区间起点与end历史最大右端点初始为第一个区间若start l and end r同时成立说明当前区间是新的一段覆盖更新start l并res 1无论是否计数都要执行end max(end, r)返回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 startstart 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起逐个递减两者都是对这一坑的显式防御。两种贪心策略对比与选型建议维度解法二起点升序终点降序解法三仅起点升序历史最大 end比较器两级键终点需降序单键天然排序即可状态变量prevL, prevR上一个保留区间start, end主导起点历史最大右端点覆盖判定prevL l and prevR r非严格start l and end r取反严格对同起点顺序的依赖强依赖终点降序保证最长在前无依赖max(end, r)吸收顺序差异时间复杂度$O(n \log n)$$O(n \log n)$选型建议手写竞赛中解法三比较器更简单、不易写错排序细节但严格/非严格不等式需要仔细推导如上文同起点更长区间的反向覆盖情形解法二逻辑直白、与区间合并系列题目的状态维护方式一致更易推广到 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

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

相关推荐

基因测序数据同步日志分析与关键字段设计实践

把 Perplexity Search SDK 的模型 Key 换成 TaoToken 后测简报

控制研究智能体长任务 Token，TaoToken 发 Key 给队列

更多资讯

Jenkins节点配置与Java Web项目CI/CD实践指南

三星M16基材+LEAD 2.0，iQOO 16的2K直屏含金量实测

吃透Java泛型：从类型擦除到PECS原则与反射实战

RRT算法在路径规划中的原理与Matlab实现

嵌入式电机控制入门：开发板避坑指南与FOC学习路线详解

DataHub Excel 连接器（Source Connector）实战指南：从工作表到数据集的元数据摄取、Schema 推断与 Profiling

今日更新

AReaL 调试指南：从 Agent Workflow 验证到分布式训练死锁诊断

MATLAB实现GPS L1 C/A信号仿真与二维捕获验证

彻底搞懂ASCII、Unicode与UTF-8：从乱码根源到编码实战

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？