LeetCode 第 5113 题：删除区间（中等）
给你一个 有序的 不相交区间列表 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
1、这里要注意：toBeRemoved 只有 1 个；
2、画图；
3、学习一下扫描线法；
4、注意讨论一下边界情况。
Java 代码：
class Solution {
public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
List<List<Integer>> res = new ArrayList<>();
int len = intervals.length;
for (int i = 0; i < len; i++) {
int left = intervals[i][0];
int right = intervals[i][1];
if (right <= toBeRemoved[0]) {
// 注意：这里是等于，此时直接把区间加到结果集里
List<Integer> interval = new ArrayList<>();
interval.add(left);
interval.add(right);
res.add(interval);
} else if (left < toBeRemoved[0] && right <= toBeRemoved[1]) {
// 注意：这里是严格小
List<Integer> interval = new ArrayList<>();
interval.add(left);
interval.add(toBeRemoved[0]);
res.add(interval);
} else if (left < toBeRemoved[0] && right > toBeRemoved[1]) {
// 注意：两边都是严格小于，才能加上两段
List<Integer> interval1 = new ArrayList<>();
interval1.add(left);
interval1.add(toBeRemoved[0]);
res.add(interval1);
List<Integer> interval2 = new ArrayList<>();
interval2.add(toBeRemoved[1]);
interval2.add(right);
res.add(interval2);
} else if (left >= toBeRemoved[0] && left <= toBeRemoved[1] && right > toBeRemoved[1]) {
// 特别注意：&& left <= toBeRemoved[1] 不要漏掉了
List<Integer> interval = new ArrayList<>();
interval.add(toBeRemoved[1]);
interval.add(right);
res.add(interval);
} else if (left >= toBeRemoved[1]) {
List<Integer> interval = new ArrayList<>();
interval.add(left);
interval.add(right);
res.add(interval);
}
}
return res;
}
}
Java 代码：
import java.util.ArrayList;
import java.util.List;
/**
* @author liweiwei1419
* @date 2019/12/1 7:41 上午
*/
public class Solution {
// 这里要注意：toBeRemoved 只有 1 个
public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
List<List<Integer>> res = new ArrayList<>();
int len = intervals.length;
for (int i = 0; i < len; i++) {
int left = intervals[i][0];
int right = intervals[i][1];
if (right <= toBeRemoved[0]) {
// 注意：这里是等于
List<Integer> interval = new ArrayList<>();
interval.add(left);
interval.add(right);
res.add(interval);
} else if (left < toBeRemoved[0] && right <= toBeRemoved[1]) {
List<Integer> interval = new ArrayList<>();
interval.add(left);
interval.add(toBeRemoved[0]);
res.add(interval);
} else if (toBeRemoved[0] <= left && right <= toBeRemoved[1]) {
// 非必需，为了语义清晰，加上
continue;
} else if (left < toBeRemoved[0] && right > toBeRemoved[1]) {
List<Integer> interval1 = new ArrayList<>();
interval1.add(left);
interval1.add(toBeRemoved[0]);
res.add(interval1);
List<Integer> interval2 = new ArrayList<>();
interval2.add(toBeRemoved[1]);
interval2.add(right);
res.add(interval2);
} else if (left >= toBeRemoved[0] && left < toBeRemoved[1]) {
// && right > toBeRemoved[1]
List<Integer> interval = new ArrayList<>();
interval.add(toBeRemoved[1]);
interval.add(right);
res.add(interval);
} else if (left >= toBeRemoved[1]) {
List<Integer> interval = new ArrayList<>();
interval.add(left);
interval.add(right);
res.add(interval);
}
}
return res;
}
}
（本节完）