[LeetCode] 1272. Remove Interval

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Constraints:

1 <= intervals.length <= 10^4
-10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

删除区间。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这也是属于扫描线一类的题目。思路也比较直接，遍历input数组，跟需要去掉的区间toBeRemoved没有重叠的子区间就直接加入结果集。如果跟toBeRemoved有重叠的部分，则比较两者的左边界和右边界来得出需要去掉的区间是什么。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         for (int[] i : intervals) {
 5             // no overlap
 6             if (i[1] <= toBeRemoved[0] || i[0] >= toBeRemoved[1]) {
 7                 res.add(Arrays.asList(i[0], i[1]));
 8             }
 9             // i[1] > toBeRemoved[0] && i[0] < toBeRemoved[1]
10             else {
11                 // left end no overlap
12                 if (i[0] < toBeRemoved[0]) {
13                     res.add(Arrays.asList(i[0], toBeRemoved[0]));
14                 }
15                 // right end no overlap
16                 if (i[1] > toBeRemoved[1]) {
17                     res.add(Arrays.asList(toBeRemoved[1], i[1]));
18                 }
19             }
20         }
21         return res;
22     }
23 }

扫描线相关题目

LeetCode 题目总结