LeetCode 1288. 删除被覆盖区间

链接

一、题目

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当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]

四、解题：

class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x: (x[0], -x[1])) # Python原地排序方法，直接修改原列表，不返回新列表 ans = 0 #用于记录未被覆盖的区间个数(即最终答案)。初始为0 max_end = -1 #用于记录目前遍历过的所有区间中，右端点的最大值。初始化为-1 for left, right in intervals: # 按排序后的顺序依次取出每个区间的左右端点 if right > max_end: # 未被覆盖 # 当满足条件时，说明当前区间是一个未被覆盖的区间，于是： ans += 1 #计数增加。 max_end = right #更新最大右端点，因为当前区间的右端点比之前所有的都大（这是由条件保证的），它成为新的最右边界。 return ans # 遍历结束后，ans就是所有未被覆盖的区间个数，即删除被覆盖区间后剩余的数量。

五、解题思路：

解题思路详解

核心思想是排序+贪心扫描，通过巧妙的排序将原本需要两两比较的覆盖关系，转化为一次从左到右的线性判断，从而高效求出答案。

5.1.问题本质回顾

-给定区间[l,r]，若存在另一个区间[L,R]满足L≤l且r≤R，则[l,r]被覆盖，应当删除。

-目标：返回剩余未被覆盖的区间个数。

5.2.核心思路：排序以简化比较

直接暴力两层循环检查每个区间是否被其他区间覆盖，时间复杂度为O(n²)，且需要处理相等边界的细节。

5.3.排序策略：左升、右降

```python

intervals.sort(key=lambda x: (x[0], -x[1]))

```

-第一关键字：左端点升序→ 保证扫描时，左边的区间起点不晚于右边的区间，这是“覆盖”的必要条件。

-第二关键字：右端点降序（即-x[1]升序）→当左端点相同时，右端点大的区间排在前面。

这样做的目的是：在起点相同的一组区间中，先处理覆盖能力最强的那个（右端点最大），确保它能正确覆盖掉后续起点相同但终点较小的区间，避免误计数。

5.4.扫描过程：维护max_end

遍历排序后的区间，用变量max_end记录到目前为止所有已扫描区间的右端点最大值。

-若当前区间right>max_end：

-说明之前的任意一个区间，即使左端点≤当前左端点，其右端点也小于当前右端点，因此不可能覆盖当前区间（因为覆盖需要右端点 ≥ 当前右端点）。

- 所以当前区间未被覆盖，答案ans加1，并更新max_end = right（因为它的右端点比之前所有都大）。

-若right≤max_end：

-说明存在某个之前的区间，其左端点≤当前左端点（排序保证），且右端点 ≥ 当前右端点（因为max_end是最大值，必≥当前右端点）。

-因此当前区间被覆盖，跳过，不计数。

5.5.复杂度分析

-时间复杂度：排序O(nlog n)，扫描O(n)，总体O(nlog n)。

-空间复杂度：原地排序，只用了常数个额外变量，O(1)。

六、sort排序

sort()函数排序