题目链接:https://leetcode.cn/problems/video-stitching/
题目大意:给出一个视频长度time
,再给出一串clips[][]
每个clip中clip[0]
代表起始时间,clip[1]
代表结束时间。求能够覆盖[0, time]
的所需的最小clip数。
思路:贪心算法。用farest[i]
代表以i
位置为起始时间能够到达的最远的结束时间(抱歉这里用“远”来形容时间,实际上把这个什么时间看成一个条带、一个区间都是一样的)。这样保证了如果该clip如果被选上,那它一定是所有相同起点内最优的那个clip。随后循环即可:
从0
开始,用last
记录当前能到达的最远的时间。那么从上一次结束的遍历位置pos
开始,在last
之前,寻找能到达的最远的时间。为什么要在last
之前呢?因为如果pos
到last
之后了,找的clip就是从last+1
开始,那其实是之后的循环要做的事情,现在不必要。相当于我们一次找到一个最优的clip,这个clip和上一个clip必定是衔接的。
然而如果一开始pos
就比last
大,说明中间必定有片段缺失了,我们无法凑成完整的[0, time]
,直接返回-1
int last = farest[0], ret = 1, pos = 0;
while (last < time && pos < time) {
if (pos > last) return -1;
int des = farest[pos], d_pos = pos;
pos++;
while (pos <= last) {
if (farest[pos] > des) {
des = farest[pos];
d_pos = pos;
}
pos++;
}
if (des > last) {
last = des;
ret++;
if (last >= time) break;
}
}
注意:题目有点坑的地方是,给出的区间可能有超过给定时间time
的clip,因此最后的返回判断应该是大于等于号文章来源:https://www.toymoban.com/news/detail-400420.html
完整代码文章来源地址https://www.toymoban.com/news/detail-400420.html
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int time) {
vector<int> farest(101, -1);
for (auto clip : clips) {
farest[clip[0]] = max(farest[clip[0]], clip[1]);
}
int last = farest[0], ret = 1, pos = 0;
while (last < time && pos < time) {
if (pos > last) return -1;
int des = farest[pos], d_pos = pos;
pos++;
while (pos <= last) {
if (farest[pos] > des) {
des = farest[pos];
d_pos = pos;
}
pos++;
}
if (des > last) {
last = des;
ret++;
if (last >= time) break;
}
}
if (last >= time)
return ret;
else
return -1;
}
};
到了这里,关于个人练习-Leetcode-1024. Video Stitching的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!