区间问题

Ⅰ 解题框架

​ 所谓区间问题，就是线段问题，让你合并所有线段、找出线段的交集等等。主要有两个技巧：
​ 1、排序。常见的排序方法就是按照区间起点排序，或者先按照起点升序排序，若起点相同，则按照终点降序排序。
​ 2、画图。就是说不要偷懒，勤动手，两个区间的相对位置到底有几种可能，不同的相对位置我们的代码应该怎么去处理。

Ⅱ 相关习题

1、删除覆盖区间（LeetCode 1288）

​ 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。在完成所有删除操作后，请你返回列表中剩余区间的数目。

​ 首先排序：按照起点升序排序，起点相同则按照终点降序排序，使用lamda表达式

//将intervals按照起点升序排序，起点相同则按照终点降序排序
        Arrays.sort(intervals,(a,b)->{
            if (a[0] == b[0]) return b[1]-a[1];
            return a[0]-b[0];
        });

image-20201213135848220

排序之后，两个相邻区间只可能有如下三种相对位置：

image-20201213135923221

​ 对于这三种情况，我们应该这样处理：对于情况一，找到了覆盖区间。对于情况二，两个区间可以合并，成一个大区间。对于情况三，两个区间完全不相交。

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        int num = intervals.length;
        //将intervals按照起点升序排序，起点相同则按照终点降序排序
        Arrays.sort(intervals,(a,b)->{
            if (a[0] == b[0]) return b[1]-a[1];
            return a[0]-b[0];
        });
        //记录线段的左右边界，初始值就是第一条线段的起点和终点
        int left = intervals[0][0];
        int right = intervals[0][1];

        //开始覆盖
        for (int i=1;i<intervals.length;i++) {
            if (intervals[i][1] <= right) { //区间被覆盖了，对应情况1
                num--;
            }else if (intervals[i][0] >= right) {//对应情况3
                left = intervals[i][0];
                right = intervals[i][1];
            }else if (right>intervals[i][0] && right<intervals[i][1]) {
                //对应情况2
                right = intervals[i][1];
            }
        }
        return num;
    }
}

2、区间合并（LeetCode 56）

​ 和第一题类似，但要注意三种情况的符号，弄清楚到底要不要加等于号

class Solution {
    public int[][] merge(int[][] intervals) {
        
        int len = intervals.length;
        List<int[]> res = new ArrayList<>();
        //排序
        Arrays.sort(intervals,(a,b)-> {
            return a[0] == b[0]?(b[1]-a[1]):(a[0]-b[0]);
        });

        int left = intervals[0][0];
        int right = intervals[0][1];
        res.add(intervals[0]);

        for (int i=1;i<len;i++) {
            if (right >= intervals[i][1]) {
                continue;
            }else if(right >= intervals[i][0] && right < intervals[i][1]) {
                right = intervals[i][1];
                //先取出修改后再重新添加
                int[] tmp = res.remove(res.size()-1);
                tmp[1] = right;
                res.add(tmp);
            } else if (right < intervals[i][0]) { //注意此处为严格小于号，不能写小于等于！
                left = intervals[i][0];
                right = intervals[i][1];
                int[] tmp2 = {left,right};
                res.add(tmp2);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

image-20201213143517525

3、区间交集问题（LeetCode 986）

​ 给定两个由一些 闭区间 组成的列表，每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）

​ 此题注意简化，不然情况太多

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int lenA = A.length;int lenB = B.length;
        if (lenA == 0 || lenB == 0) return new int[0][0];

        int indexA = 0;int indexB = 0;
        List<int[]> res = new ArrayList<>();
        while (indexA < lenA && indexB <lenB) {
            //可以这样简化！！！
            int lo = Math.max(A[indexA][0],B[indexB][0]);
            int hi = Math.min(A[indexA][1],B[indexB][1]);

            if (lo<=hi) {
                res.add(new int[]{lo,hi});
            }
            //谁的右边小，谁的指针就右移
            if (A[indexA][1]>=B[indexB][1]) {
                indexB++;
            }else {
                indexA++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

区间贪心算法

4、无重叠区间（LeetCode 435）

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

image

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {

        if (intervals.length == 0) return 0;
        return intervals.length-interval(intervals);
    }

    int interval (int[][] intervals) {
        int res = 1;
        Arrays.sort(intervals,(a,b)->{
            return a[1]-b[1];
        }); 
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i=1;i<intervals.length;i++) {
            if (end <= intervals[i][0]) {
                res++;
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        return res;
    }
}

5、用箭引爆气球（LeetCode 452）

与上一题不同的是两个区间交集为一个点时还是算作一个区间

class Solution {
    public int findMinArrowShots(int[][] points) {

        if (points.length == 0) return 0;
        Arrays.sort(points,(a,b)->{
            //不要用return a[1]-b[1];  会发生溢出
            return a[1] > b[1] ? 1 : -1;
        });
        int res = 1;
        int start = points[0][0];
        int end = points[0][1];
        for (int i=1;i<points.length;i++) {
            if (end < points[i][0]) {
                res++;
                start = points[i][0];
                end = points[i][1];
            }
        }
        return res;
    }
}