関小君刷题记

题目大意：

删除区间

给你一个 有序的 不相交区间列表 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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1272

解题思路分析：

本题无非3种情况：

1. 当删除区间的开始下标在当前区间内时，当前区间开始位置到删除区间开始位置会被分割成一个新的区间
2. 当删除区间的结束下标在当前区间内时，删除区间结束位置到当前区间结束位置会被分割成一个新的区间
3. 如果当前区间与删除区间没有交集，那么当前区间是一个合理区间。

除以上情况之外再无其他可能。

实现代码：

public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
    List<List<Integer>> res = new ArrayList<>(); // 返回结果
    for(int[] interval : intervals){ // 循环每一个区间
        // 删除区间的开始下标在当前区间内
        if(toBeRemoved[0]>interval[0] && toBeRemoved[0]<interval[1]){
            List<Integer> list=new ArrayList<>();
            list.add(interval[0]);
            list.add(toBeRemoved[0]);
            res.add(list);
        }
        // 删除区间的结束下标在当前区间内
        if(toBeRemoved[1]<interval[1] && toBeRemoved[1]>interval[0]){
            List<Integer> list=new ArrayList<>();
            list.add(toBeRemoved[1]);
            list.add(interval[1]);
            res.add(list);
        }
        // 当前区间与删除区间没有交集
        if(toBeRemoved[0]>=interval[1] || interval[0]>=toBeRemoved[1]){
            List<Integer> list=new ArrayList<>();
            list.add(interval[0]);
            list.add(interval[1]);
            res.add(list);
        }
    }
    return res;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 76.48% of Java online submissions for Remove Interval.

Memory Usage: 58.1 MB, less than 100.00% of Java online submissions for Remove Interval.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1272-remove-interval-解题思路分析/