企业官网建设流程全解析

【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 <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• 对于所有的i != j：intervals[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 ) n=len(intervals)n=len(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(vector<vector<int>>&intervals){sort(intervals.begin(),intervals.end(),[](constvector<int>&a,constvector<int>&b){returna[0]==b[0]?a[1]>b[1]:a[0]<b[0];});intans=intervals.size();for(inti=0,n=intervals.size(),r=0;i<n;i++){ans-=intervals[i][1]<=r;r=max(r,intervals[i][1]);}returnans;}};

Python

''' LastEditTime: 2026-07-07 22:19:44 '''fromtypingimportListclassSolution:defremoveCoveredIntervals(self,intervals:List[List[int]])->int:intervals.sort(key=lambdax:(x[0],-x[1]))ans=len(intervals)R=0forl,rinintervals:ans-=r<=R R=max(R,r)returnans

Java

/* * @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];});intans=intervals.length;intr=0;for(int[]v:intervals){if(v[1]<=r){ans--;}else{r=v[1];}}returnans;}}

Go

/* * @LastEditTime: 2026-07-07 22:28:57 */packagemainimport"sort"funcremoveCoveredIntervals(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}r=max(r,v[1])}returnans}

Rust

/* * @LastEditTime: 2026-07-07 22:36:22 */implSolution{pubfnremove_covered_intervals(mutintervals:Vec<Vec<i32>>)->i32{intervals.sort_by_key(|x|(x[0],-x[1]));letmutans=intervals.len()asi32;letmutr=0;forvinintervals.iter(){ifv[1]<=r{ans-=1;}else{r=v[1];}}returnans;}}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源