区间相关问题

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;
    }
};

func removeCoveredIntervals(intervals [][]int) int {
    n := len(intervals)
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] == intervals[j][0] {
            return intervals[i][1] < intervals[j][1]
        }
        return intervals[i][0] < intervals[j][0]
    })
    res := 0
    l := intervals[0][0] //左端点
    r := intervals[0][1] //右端点

    for 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);

func merge(intervals [][]int) [][]int {
    //按照起点升序排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    n := len(intervals)
    res := [][]int{}
    l := intervals[0][0] //左端点
    r := intervals[0][1] //右端点

    for i := 1; i < n; i++ {
        if intervals[i][0] > r { //当前区间和上一个区间没有交集
            res = append(res, []int{l, r})
            //更新左右端点
            l = intervals[i][0]
            r = intervals[i][1]
        } else { //当前区间和上一个区间有交集
            //左端点不变，右端点更新为 max(r, intervals[i][1])
            if intervals[i][1] > r {
                r = intervals[i][1]
            }
        }
    }
    //最后再将最后一个合并或者未合并的独立区间[l,r]加入答案数组中
    res = append(res, []int{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;
    }
};

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    res := [][]int{}
    m := len(firstList)
    n := len(secondList)

    //双指针
    i := 0
    j := 0
    for i < m && j < n {
        a1 := firstList[i][0]
        a2 := firstList[i][1]
        b1 := secondList[j][0]
        b2 := secondList[j][1]

        //两个区间存在交集
        if a1 <= b2 && a2 >= b1 {
            //计算交集，加入res
            maxStart := a1
            if b1 > a1 {
                maxStart = b1
            }
            minEnd := a2
            if b2 < a2 {
                minEnd = b2
            }
            res = append(res, []int{maxStart, minEnd})
        }
        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;
    }
};

func videoStitching(clips [][]int, time int) int {
    if time == 0 {
        return 0
    }
    //按起点升序排序，起点相同的按终点降序排序；
    sort.Slice(clips, func(i, j int) bool {
        if clips[i][0] == clips[j][0] {
            return clips[i][1] > clips[j][1]
        }
        return clips[i][0] < clips[j][0]
    })

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

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