题目描述

给你一个 有序的 不相交区间列表 intervals 和一个要删除的区间 toBeRemoved，intervals 中的每一个区间 intervals[i] = [a, b] 都表示满足 a <= x < b 的所有实数 x 的集合。

我们将 intervals 中任意区间与 toBeRemoved 有交集的部分都删除。

返回删除所有交集区间后，intervals 剩余部分的 有序 列表。

样例

输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
输出：[[0,1],[6,7]]

输入：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

算法

(线性扫描) $O(n)$

1. 线性扫描每个区间，如果当前区间和待删除区间不相交，则直接加入答案集合。
2. 如果当前区间和待删除区间相交：这里可能有两种情况，一种是当前区间左端点 x 小于待删除区间的左端点 mx，则往答案集合中添加 [x, mx)；另一种是当前区间右端点 y 大于待删除区间的左端点 my，则往答案集合中添加 [my, y)。

时间复杂度

• 只需要扫描一般整个区间集合，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的空间存储答案，故空间复杂度也为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> ans;
        int mx = toBeRemoved[0], my = toBeRemoved[1];
        for (const auto &i : intervals) {
            int x = i[0], y = i[1];
            if (y <= mx || x >= my) ans.push_back(i);
            else {
                if (x < mx) ans.push_back({x, mx});
                if (y > my) ans.push_back({my, y});
            }
        }
        return ans;
    }
};