Question

1272. 删除区间

English Version

题目描述

实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 [a, b)（左闭右开），表示满足 a <= x < b 的所有实数  x 的集合。如果某个区间 [a, b) 中包含实数 x ，则称实数 x 在集合中。

给你一个 有序的 不相交区间列表 intervals 。intervals 表示一个实数集合，其中每一项 intervals[i] = [ai, bi] 都表示一个区间 [ai, bi) 。再给你一个要删除的区间 toBeRemoved 。

返回 _一组实数，该实数表示intervals 中 删除 了 toBeRemoved 的部分_ 。_换句话说，返回实数集合，并满足集合中的每个实数 x 都在 intervals 中，但不在 toBeRemoved 中。你的答案应该是一个如上所述的 有序的 不相连的间隔列表 。_

 

 

示例 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]]

示例 3：

输入：intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
输出：[[-5,-4],[-3,-2],[4,5],[8,9]]

 

提示：

• 1 <= intervals.length <= 104
• -109 <= ai < bi <= 109

解法

方法一：分类讨论

我们记要删除的区间为 $[x, y)$，遍历区间列表，对于每个区间 $[a, b)$，有以下三种情况：

• $a \geq y$ 或 $b \leq x$，表示该区间与要删除的区间没有交集，直接将该区间加入答案；
• $a \lt x$, $b \gt y$，表示该区间与要删除的区间有交集，将该区间分成两个区间加入答案；
• $a \geq x$, $b \leq y$，表示该区间被要删除的区间完全覆盖，不加入答案。

时间复杂度 $O(n)$，其中 $n$ 为区间列表的长度。空间复杂度 $O(1)$。

class Solution:
  def removeInterval(
    self, intervals: List[List[int]], toBeRemoved: List[int]
  ) -> List[List[int]]:
    x, y = toBeRemoved
    ans = []
    for a, b in intervals:
      if a >= y or b <= x:
        ans.append([a, b])
      else:
        if a < x:
          ans.append([a, x])
        if b > y:
          ans.append([y, b])
    return ans

class Solution {
  public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
    int x = toBeRemoved[0], y = toBeRemoved[1];
    List<List<Integer>> ans = new ArrayList<>();
    for (var e : intervals) {
      int a = e[0], b = e[1];
      if (a >= y || b <= x) {
        ans.add(Arrays.asList(a, b));
      } else {
        if (a < x) {
          ans.add(Arrays.asList(a, x));
        }
        if (b > y) {
          ans.add(Arrays.asList(y, b));
        }
      }
    }
    return ans;
  }
}

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

func removeInterval(intervals [][]int, toBeRemoved []int) (ans [][]int) {
  x, y := toBeRemoved[0], toBeRemoved[1]
  for _, e := range intervals {
    a, b := e[0], e[1]
    if a >= y || b <= x {
      ans = append(ans, e)
    } else {
      if a < x {
        ans = append(ans, []int{a, x})
      }
      if b > y {
        ans = append(ans, []int{y, b})
      }
    }
  }
  return
}