56.合并区间 | 1288.删除被覆盖的区间 | 986.区间列表的交集

56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路：
一文秒杀所有区间相关问题

区间问题先排序，所有区间按起点升序排，起点相同的按终点降序排

 排好之后的区间有三种情况：1.覆盖    2.相交   3.完全不相交

2.相交 

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b)
    {
        if(a[0]==b[0])
            return a[1]>b[1];
        else
            return a[0]0];
    }
    vectorint>> merge(vectorint>>& intervals) {
        //所有区间按起点升序排，起点相同的按终点降序排
        sort(intervals.begin(),intervals.end(),cmp);
        int left=intervals[0][0];
        int right=intervals[0][1];
        vectorint>> res;
        for(int i=1;isize();i++)
        {
            //两区间相交，合并成一个大区间
            if(intervals[i][0]<=right&&intervals[i][1]>=right)
            {
                right=intervals[i][1];
            }
            //两区间完全不相交，将之前的{left,right}加入结果中，更新left和right
            if(intervals[i][0]>right&&intervals[i][1]>right)
            {
                res.push_back({left,right});
                left=intervals[i][0];
                right=intervals[i][1];
            }
        }
        //把最后一组{left,right}加入结果中
        res.push_back({left,right});
        return res;
    }
};

1288.删除被覆盖的区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。 

1.覆盖 

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b)
    {
        if(a[0]==b[0])
            return a[1]>b[1];
        else
            return a[0]0];
    }
    int removeCoveredIntervals(vectorint>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);//排序
        int left=intervals[0][0];
        int right=intervals[0][1];
        int del=0;
        for(int i=1;isize();i++)
        {
            //覆盖，要删除的区间数加一
            if(intervals[i][0]>=left&&intervals[i][1]<=right)
            {
                del++;
            }
            //除覆盖以外的其他情况，更新{left，right}
            else 
            {
                left=intervals[i][0];
                right=intervals[i][1];
            }
        }
        return intervals.size()-del;//剩余区间数=总数-要删除区间数
    }
};

986.区间列表的交集 

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

class Solution {
public:
    vectorint>> intervalIntersection(vectorint>>& firstList, vectorint>>& secondList) {
        vectorint>> res;
        int i=0;
        int j=0;
        while(isize()&&jsize())
        {
            int a1=firstList[i][0];
            int a2=firstList[i][1];
            int b1=secondList[j][0];
            int b2=secondList[j][1];
            if(b1<=a2&&b2>=a1)//相交或覆盖时，取交集(左边界取大的那个，右边界取小的那个)
            {
                int left=max(a1,b1);
                int right=min(a2,b2);
                res.push_back({left,right});
            }
            if(b2<=a2)//secondList[j]在firstList[i]的左边，所以j++
                j++;
            else//...在...的右边，所以i++
                i++;
        }
        return res;
    }
};