1272.删除区间

Difficulty
Medium
Tags
扫描线
URL
Star
给你一个 有序的 不相交区间列表 intervals 和一个要删除的区间toBeRemoved， intervals 中的每一个区间 intervals[i] = [a, b] 都表示满足 a <= x < b 的所有实数 x 的集合。
我们将 intervals 中任意区间与 toBeRemoved 有交集的部分都删除。
返回删除所有交集区间后， intervals 剩余部分的有序 列表。
示例1
输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
输出：[[0,1],[6,7]]
示例2
输入：intervals = [[0,5]], toBeRemoved = [2,3]
输出：[[0,2],[3,5]]
提示：
  • 1 <= intervals.length <= 10^4
  • 10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

法1 扫描线

思路
遍历intervals 中的interval, toBeRemoved 和 interval 共有以下几种情况：
  1. toBeRemoved 在interval 后面。即toBeRemoved[0] > interval[1]
      2. 此时，必然没有交集，直接将interval 添加到res即可
  1. toBeRemoved 在interval 前面。即toBeRemoved[1] < interval[0]
      2. 此时，必然没有交集，直接将interval 添加到res即可
  1. interval 的后半部分都在toBeRemoved 中
      2. 此时，将 [interval[0], toBeRemoved[0]]添加到res数组中。且继续向后遍历intervals
  1. interval 的前半部分都在toBeRemoved 中
      2. 此时，将 [interval[1], toBeRemoved[1]]添加到res数组中。且将intervals中的后续区间直接添加到res中
  1. interval 的中间部分都在toBeRemoved 中
      2. 此时，返回两头没有被包的部分即可。之后可以将intervals中的后续区间直接添加到res中
  1. interval 完全在toBeRemoved 中
      2. 跳过该区间，遍历下一个区间
题解
class Solution:
    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
        res = []
        for i, j in intervals:
            if toBeRemoved[0] >= j or toBeRemoved[1] <= i:
                res.append([i, j])
            else:
                if toBeRemoved[0] > i:
                    res.append([i, toBeRemoved[0]])
                if toBeRemoved[1] < j:
                    res.append([toBeRemoved[1], j])
        return res