LeetCode 1024 Video Stitching

Tag: 贪心法 LeetCode Posted on 2022-02-21 17:27:04 Edited on 2022-02-21 21:30:07 Views: 142

概述

https://leetcode.com/problems/video-stitching/

贪心法

对所有区间按前端点升序排序,如果前端点相同则按后端点降序排序。

对于第一个前端点,我们必然要该区间,之后找出与其重叠的其他所有区间中后端点最远的区间,选择该区间为下一个区间,以此类推。

所以我们应该依然是按后端点进行排序。

所以可以设置一个 dummy 区间,其范围为 [-1, 0]。


醉了,当时没写完吃饭回来,现在过了几个小时我思路断了。

不浪费时间了(32 / 60 test cases passed):

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        clips.push_back({-1, 0});
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) -> bool {
           return a[1] < b[1]; 
        });
        int lastEnd = 0;
        int candidate = 0;
        int count = 0;
        for (auto& c : clips) {
            if (c[0] <= lastEnd) {
                candidate = max(candidate, c[1]);
            } else {
                lastEnd = candidate;
                count ++;
                if (lastEnd < c[0]) return -1;
                candidate = max(candidate, c[1]);
            }
        }
        if (candidate < time) return -1;
        return count;
    }
};

贪心法(总是选择候选者里最远的那个)

https://labuladong.gitee.io/algo/3/27/106/

这里要注意的是,当循环结束后,我们还需要额外更新一次 count。

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) -> bool {
            if (a[0] != b[0]) return a[0] < b[0]; 
            else return a[1] > b[1];
        });
        if (clips[0][0] != 0) return -1;
        int count = 1;
        int curEnd = clips[0][1];
        int nextEnd = 0;
        for (auto& c : clips) {
            if (c[0] <= curEnd) {
                nextEnd = max(nextEnd, c[1]);
            } else {
                curEnd = nextEnd;
                count ++;
                if (curEnd < c[0]) return -1;
                nextEnd = max(nextEnd, c[1]);
            }
            if (curEnd >= time) return count;
        }
        if (nextEnd >= time) return count + 1;
        return -1;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/