Solutions CS101

Appearance

M1288.删除被覆盖区间 ​

greedy, 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]

这题用 排序 + 一次扫描。

结论： 先把区间按 左端点升序、右端点降序 排序；然后维护目前扫到的最大右端点 max_r。
若当前区间 r <= max_r，说明它被前面的某个区间覆盖；否则保留并更新 max_r。

python
from typing import List

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        
        ans = 0
        max_r = -1
        
        for l, r in intervals:
            if r <= max_r:
                continue
            ans += 1
            max_r = r
        
        return ans

思路要点：

  • 先按左端点升序排，这样后面的区间左端点一定不小于前面。
  • 若左端点相同，要按右端点降序排；这样更长的区间会排在前面，后面短的才会被正确识别为“被覆盖”。
  • 扫描时只需看右端点：若当前 r <= max_r，就存在前面区间 [c, d) 满足 c <= a 且 b <= d。
  • 否则当前区间不能被覆盖，应保留，并更新 max_r = r。

复杂度：

  • 排序 O(n log n)
  • 扫描 O(n)
  • 总复杂度 O(n log n)，额外空间若不算排序栈为 O(1)

为什么必须右端点降序？ 比如 [[1,4],[1,3]]

  • 如果左端点相同还按右端点升序排，会先看到 [1,3]，再看到 [1,4]，就不容易判断 [1,3] 被覆盖。
  • 降序排成 [1,4],[1,3] 后，[1,3] 的右端点 3 <= 4，自然就判掉了。