1288. 删除被覆盖区间

Difficulty
Medium
Tags
扫描线
URL
https://leetcode-cn.com/problems/remove-covered-intervals/
Star
给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 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]

法1 扫描线

思路
将区间按照开始时间升序排列，结束时间降序排列。那么如果发生覆盖只有如下情况：
notion imagenotion image
这四种情况有一个共同点：next[1] ≤ cur[1]
所以根据这个共同的来判断有无覆盖。
题解
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) <= 1:
            return len(intervals)

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

        count = 1
        last = intervals[0]
        for cur in intervals[1:]:
            if cur[1] > last[1]:
                last = cur
                count += 1

        return count