您现在的位置:首页 > >

Leetcode刷题 1024.Video Stitching 拼接视频

发布时间:



Leetcode 1024.Video Stitching
题目解题思路参考解法暴力dp1、 最优子结构/状态转移公式2、边界
贪心
总结


题目

【 英文 】:You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.


Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].


Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.


【 题意 】:你将会获得一系列视频片段,这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。


视频片段 clips[i] 都用区间进行表示:开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。


我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, T])。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。


解题思路

多角度解题,这里说一下贪心的思路:
可选择从0或这末尾时间开始拼接,一次遍历数组,在满足小于(大于)当前拼接时间的情况下,尽可能的延长尽头的时间,再以最大(最小)尽头的时间再进行拼接选择。直至拼接完成。



参考解法
暴力

class Solution {
public:
int minnum=INT_MAX;
Solution(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int videoStitching(vector>& clips, int T) {
int flag[clips.size()]={0};
int curmin=0;
int curt=0;
recStitching(clips,T,flag,curmin,curt);
if(minnum==INT_MAX)
return -1;
return minnum;
}
void recStitching(vector>& clips, int T,int flag[],int curmin,int curt){
if(curt>=T){
if(curmin minnum=curmin;
return;
}
if(curmin>minnum)
return;
for(int i=0;i
//没用过
if(flag[i]==0&&clips[i][0]<=curt&&clips[i][1]>curt){
flag[i]==1;
recStitching(clips,T,flag,curmin+1,clips[i][1]);
flag[i]==0;
}
}
}
};

这种方法直接Time Limit Exceeded


dp
1、 最优子结构/状态转移公式

前提:能够拼出视频
F(T)=min(F(T),F(C[0])+1)


2、边界

F(0)=0


#include
#include

using namespace std;
class Solution {
public:
Solution(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int videoStitching(vector>& clips, int T) {
int F[T+1];
for(int i=0;i<=T;i++){
F[i]=i+1;
}
F[0]=0;
for(int i=0;i<=T;i++){
for(auto clip:clips){
if(clip[0]=i&&F[clip[0]]!=clip[0]+1){
F[i]=min(F[clip[0]]+1,F[i]);
}

}
}
if(F[T]==T+1)
return -1;
return F[T];
}
};

【 时间复杂度 】两个循环 O(T*n)
【 空间复杂度 】新开辟的最优解组 O(T)


贪心

class Solution {
public:
int videoStitching(vector>& clips, int T) {
sort(clips.begin(),clips.end());
int curT=0,curmax=0,sum=0;
for(auto clip:clips){
if(curmax>=T)
break;
if(clip[0]<=curT&&clip[1]>curmax){
curmax=clip[1];
}
if(clip[0]>curT&&clip[0]
sum++;
curT=curmax;
curmax=max(clip[1],curmax);
}else if(clip[0]>curT&&clip[0]>curmax)
return -1;
}
if(curmax return -1;
sum++;
return sum;
}
};

【 输出结果 】


总结

没啥好说的多练题吧!对c++还不是很熟。



热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报