区间问题小结

1288. 删除被覆盖区间

题目问我们，去除被覆盖区间之后，还剩下多少区间，那么我们可以先算一算，被覆盖区间有多少个，然后和总数相减就是剩余区间数。
还是先排序：按照开始Start排序：

排序后相邻的两个区间有三种状态：

对于这三种情况，我们应该这样处理：
对于情况一，找到了覆盖区间。
对于情况二，两个区间可以合并，成一个大区间。
对于情况三，两个区间完全不相交。
依据几种情况，我们可以写出如下代码：

int removeCoveredIntervals(int[][] intvs) {
    // 按照起点升序排列，起点相同时降序排列
    Arrays.sort(intvs, (a, b) -> {
        if (a[0] == b[0]) {
            return b[1] - a[1];
        }
        return a[0] - b[0]; 
    });
    // 记录合并区间的起点和终点
    int left = intvs[0][0];
    int right = intvs[0][1];
    int res = 0;
    for (int i = 1; i < intvs.length; i++) {
        int[] intv = intvs[i];
        // 情况一，找到覆盖区间
        if (left <= intv[0] && right >= intv[1]) {
            res++;
        }
        // 情况二，找到相交区间，合并
        if (right >= intv[0] && right <= intv[1]) {
            right = intv[1];
        }
        // 情况三，完全不相交，更新起点和终点
        if (right < intv[0]) {
            left = intv[0];
            right = intv[1];
        }
    }
    return intvs.length - res;
}

起点升序排列，终点降序排列的目的是防止如下情况

56. 合并区间

参leetcode

一般思路是先排序 选择按start排序。

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        //按区间的 start 升序排列
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] curr = intervals[i];
            // res 中最后一个元素的引用
            int[] last = res.getLast();
            if (curr[0] <= last[1]){//只需要比较右边即可，因为我们已经排序
                last[1] = Math.max(curr[1],last[1]);//更新数组边界
            }else {
                // 处理下一个待合并区间
                res.add(curr);
            }
        }
        return res.toArray(new int[0][0]);
    }
}

986. 区间列表的交集

详细参考了labuladong

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        LinkedList<int[]> res = new LinkedList<>();
        //两个指针
        int i = 0;
        int j = 0;
        while (i< firstList.length && j < secondList.length){
            int a1 = firstList[i][0], a2 = firstList[i][1];
            int b1 = secondList[j][0], b2 = secondList[j][1];
            if (b2 >= a1 && a2 >= b1){//有交集的情况
                //计算出交集，加入 res
                res.add(new int[]{
                        Math.max(a1, b1), Math.min(a2, b2)
                });
            }
            if (b2 < a2) {
                j++;
            } else {
                i++;
            }
        }
        return res.toArray(new int[0][0]);
    }
}

1024. 视频拼接

区间问题肯定按照区间的起点或者终点进行排序。

先按照起点升序排序，如果起点相同的话按照终点降序排序。
原因：
1、要用若干短视频凑出完成视频[0, T]，至少得有一个短视频的起点是 0。
这个很好理解，如果没有一个短视频是从 0 开始的，那么区间[0, T]肯定是凑不出来的。
2、如果有几个短视频的起点都相同，那么一定应该选择那个最长（终点最大）的视频。

基于以上两个特点，将clips按照起点升序排序，起点相同的按照终点降序排序，最后得到的区间顺序就像这样：

这样我们就可以确定，如果clips[0]是的起点是 0，那么clips[0]这个视频一定会被选择。

当我们确定clips[0]一定会被选择之后，就可以选出第二个会被选择的视频：
我们会比较所有起点小于clips[0][1]的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频。
然后可以通过第二个视频区间贪心选择出第三个视频，以此类推，直到覆盖区间[0, T]，或者无法覆盖返回 -1。
为了实现我们需要两个变量

class Solution {
    public int videoStitching(int[][] clips, int T) {
        if (T == 0) return 0;
        // 按起点升序排列，起点相同的降序排列
        // PS：其实起点相同的不用降序排列也可以，不过我觉得这样更清晰
        Arrays.sort(clips, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        // 记录选择的短视频个数
        int res = 0;

        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.length;
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个视频的区间内贪心选择下一个视频
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++;
            }
            // 找到下一个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if (curEnd >= T) {
                // 已经可以拼出区间 [0, T]
                return res;
            }
        }
        // 无法连续拼出区间 [0, T]
        return -1;
    }
}
// 详细解析参见：
// https://labuladong.github.io/article/?qno=1024