区间相关问题

1288.删除被覆盖区间、56.合并区间、986.区间列表的交集、1024.视频拼接

1288.删除被覆盖区间

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n=intervals.size();
        sort(intervals.begin(), intervals.end());
        int res=0;
        int l = intervals[0][0]; //左端点
        int r = intervals[0][1]; //右端点

        for(int i=1;i<n;i++){
            //下一个区间覆盖上一个
            if(intervals[i][0]>=l && intervals[i][1]<=r){
                res++;
            }
            //上一个区间覆盖下一个
            else if(intervals[i][0]==l && intervals[i][1]>=r){
                res++;
                l = intervals[i][0];
                r = intervals[i][1];
            }
            //下一个区间和上一个区间相交或者没有交集
            else{
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        return n-res;
    }
};

56.合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //按照起点升序排序
        sort(intervals.begin(), intervals.end());
        int n=intervals.size();
        vector<vector<int>> res;
        int l=intervals[0][0]; //左端点
        int r=intervals[0][1]; //右端点

        for(int i=1;i<n;i++){
            if(intervals[i][0]>r){ //当前区间和上一个区间没有交集
                res.push_back({l, r}); 
                //更新左右端点
                l=intervals[i][0]; 
                r=intervals[i][1];
            }else{ //当前区间和上一个区间有交集
                //左端点不变，右端点更新为 max(r, intervals[i][1])
                r = max(r, intervals[i][1]);
            }
        }
        //最后再将最后一个合并或者未合并的独立区间[l,r]加入答案数组中
        res.push_back({l, r});
        return res;
    }
};
//时间复杂度O(nlogn);
//空间复杂度O(n);

986.区间列表的交集

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,         		vector<vector<int>>& secondList) {
        vector<vector<int>> res;
        int m=firstList.size();
        int n=secondList.size();

        //双指针
        int i=0;
        int j=0;
        while(i<m && j<n){
            int a1 = firstList[i][0];
            int a2 = firstList[i][1];
            int b1 = secondList[j][0];
            int b2 = secondList[j][1];

            //两个区间存在交集
            if(a1<=b2 && a2>=b1){
                //计算交集，加入res
                res.push_back({max(a1, b1), min(a2, b2)});
            }
            if(b2<a2){
                j++;
            }else{
                i++;
            }
        }
        return res;
    }
};

1024.视频拼接

class Solution {
public:
    static bool Comp(vector<int>& a, vector<int>& b){
            if(a[0]==b[0]){
                return a[1]>b[1];
            }
            return a[0]<b[0];
        }
    int videoStitching(vector<vector<int>>& clips, int time) {
        if(time==0) return 0;
        //按起点升序排序，起点相同的按终点降序排序；
        sort(clips.begin(), clips.end(), Comp);

        //记录选择的短视频个数
        int res=0;

        int curEnd=0, nextEnd=0;
        int n=clips.size();
        int i=0;
        while(i<n && clips[i][0]<=curEnd){
            // 在第 res 个视频的区间内贪心选择下一个视频
            while(i<n && clips[i][0]<=curEnd){
                nextEnd = max(nextEnd, clips[i][1]);
                i++;
            }
            //找到下一个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if(curEnd>=time){
                //已经可以拼出区间[0, time]
                return res;
            }
        }
        //无法拼出
        return -1;
    }
};