LeetCode 1024 Video Stitching
概述
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;
}
};