---

1288. 删除被覆盖区间

• 标签：数组、排序
• 难度：中等

题目链接

• 1288. 删除被覆盖区间 - 力扣

题目大意

描述：给定一个区间列表 $intervals$，其中 $intervals[i] = [l_i, r_i]$。如果区间 $a$ 被区间 $b$ 覆盖（即 $l_b \le l_a$ 且 $r_b \ge r_a$），那么区间 $a$ 就是冗余的。

要求：移除所有被其他区间覆盖的区间后，返回剩余区间的数量。

说明：

• $1 \le intervals.length \le 1000$。
• $0 \le l_i < r_i \le 10^{5}$。

示例：

• 示例 1：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：[1,4] 和 [3,6] 都被 [2,8] 覆盖，移除后剩下 2 个。

• 示例 2：

输入：intervals = [[1,4],[2,3]]
输出：1
解释：[2,3] 被 [1,4] 覆盖，移除后剩下 1 个。

解题思路

思路 1：排序 + 贪心

1. 核心思想

判断一个区间是否被覆盖，需要看是否存在另一个区间左端点小于等于它且右端点大于等于它。

先对区间排序：按左端点升序排列，如果左端点相同，按右端点降序排列。

左端点升序意味着遍历时后面的区间左端点 $\ge$ 前面的区间左端点。按右端点降序是为了处理左端点相同的情况：左端点相同时，右端点更大的区间会先出现，这样前面的区间会覆盖后面的区间。

遍历过程中，维护当前"覆盖范围"的最大右端点 $max\_r$。如果当前区间的右端点 $\le max\_r$，说明被覆盖；否则，它是一个新的未被覆盖的区间。

2. 具体步骤

第 1 步：将 $intervals$ 按左端点升序、右端点降序排序。

第 2 步：初始化 $max\_r = -1$ 和 $count = 0$。

第 3 步：遍历每个区间 $[l, r]$：

• 如果 $r > max\_r$：这是一个未被覆盖的区间，$count += 1$，$max\_r = r$。
• 否则（$r \le max\_r$）：被覆盖，跳过。

第 4 步：返回 $count$。

3. 结合示例走一遍

$intervals = [[1,4],[3,6],[2,8]]$

排序后（左升序，左相同则右降序）：$[[1,4],[2,8],[3,6]]$

遍历：

• $[1,4]$：$r=4 > max\_r=-1$ → $count=1$，$max\_r=4$
• $[2,8]$：$r=8 > max\_r=4$ → $count=2$，$max\_r=8$
• $[3,6]$：$r=6 \le max\_r=8$ → 被覆盖，跳过

$count=2$。

$intervals = [[1,4],[2,3]]$

排序后：$[[1,4],[2,3]]$

遍历：

• $[1,4]$：$r=4 > max\_r=-1$ → $count=1$，$max\_r=4$
• $[2,3]$：$r=3 \le max\_r=4$ → 被覆盖，跳过

$count=1$。

思路 1：代码

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # 按左端点升序，左端点相同则按右端点降序
        intervals.sort(key=lambda x: (x[0], -x[1]))

        count = 0
        max_r = -1
        for l, r in intervals:
            if r > max_r:
                count += 1
                max_r = r
            # else: 被覆盖，跳过

        return count

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是区间数量。排序需要 $O(n \log n)$，遍历需要 $O(n)$。
• 空间复杂度：$O(1)$，只使用了常数个变量。