LeetCode 1288.删除被覆盖区间：排序(非二重循环暴力)

【LetMeFly】1288.删除被覆盖区间排序(非二重循环暴力)力扣题目链接https://leetcode.cn/problems/remove-covered-intervals/给你一个区间列表请你删除列表中被其他区间所覆盖的区间。只有当c a且b d时我们才认为区间[a,b)被区间[c,d)覆盖。在完成所有删除操作后请你返回列表中剩余区间的数目。示例输入intervals [[1,4],[3,6],[2,8]]输出2解释区间 [3,6] 被区间 [2,8] 覆盖所以它被删除了。提示​​​​​​1 intervals.length 10000 intervals[i][0] intervals[i][1] 10^5对于所有的i ! jintervals[i] ! intervals[j]解题方法一二重循环暴力由于数据量最大只有1000 10001000所以可以二重循环一一对比查看某个区间是否被包含在其他区间中。时间复杂度O ( n 2 ) O(n^2)O(n2)其中n l e n ( i n t e r v a l s ) nlen(intervals)nlen(intervals)空间复杂度O ( 1 ) O(1)O(1)解题方法二排序贪心按照其实时间从小到大排序那么按顺序遍历的过程中后遍历的区间起始时间一定比先遍历区间的晚。那么如果前面有区间的截止时间在此区间之后是不是说明这个区间一定被覆盖掉了。所以排序依据若起始时间不同则起始时间小的优先否则截止时间大的优先。时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)空间复杂度O ( log ⁡ n ) O(\log n)O(logn)AC代码C/* * LastEditTime: 2026-07-07 22:16:53 */classSolution{public:intremoveCoveredIntervals(vectorvectorintintervals){sort(intervals.begin(),intervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0]?a[1]b[1]:a[0]b[0];});intansintervals.size();for(inti0,nintervals.size(),r0;in;i){ans-intervals[i][1]r;rmax(r,intervals[i][1]);}returnans;}};Python LastEditTime: 2026-07-07 22:19:44 fromtypingimportListclassSolution:defremoveCoveredIntervals(self,intervals:List[List[int]])-int:intervals.sort(keylambdax:(x[0],-x[1]))anslen(intervals)R0forl,rinintervals:ans-rR Rmax(R,r)returnansJava/* * LastEditTime: 2026-07-07 22:31:39 */importjava.util.Arrays;classSolution{publicintremoveCoveredIntervals(int[][]intervals){Arrays.sort(intervals,(a,b)-{returna[0]b[0]?b[1]-a[1]:a[0]-b[0];});intansintervals.length;intr0;for(int[]v:intervals){if(v[1]r){ans--;}else{rv[1];}}returnans;}}Go/* * LastEditTime: 2026-07-07 22:28:57 */packagemainimportsortfuncremoveCoveredIntervals(intervals[][]int)int{sort.Slice(intervals,func(i,jint)bool{ifintervals[i][0]intervals[j][0]{returnintervals[i][1]intervals[j][1]}returnintervals[i][0]intervals[j][0]})ans:len(intervals)r:0for_,v:rangeintervals{ifv[1]r{ans-1}rmax(r,v[1])}returnans}Rust/* * LastEditTime: 2026-07-07 22:36:22 */implSolution{pubfnremove_covered_intervals(mutintervals:VecVeci32)-i32{intervals.sort_by_key(|x|(x[0],-x[1]));letmutansintervals.len()asi32;letmutr0;forvinintervals.iter(){ifv[1]r{ans-1;}else{rv[1];}}returnans;}}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源