首页 > 其他 > 详细

1024. 视频拼接

时间:2020-11-18 14:40:38      阅读:23      评论:0      收藏:0      [点我收藏+]

题目:视频片段 clips[i] 都用区间进行表示:开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, T])。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。
解法一:动态规划
思路:数学符号: dp[i]表示覆盖[0,i]所需的最小片段数;状态转移方程:从所有能到达i的片段j中,找最小的dp[j的起点],再加1就是dp[i],即dp[i] = Math.min(dp[i],dp[clips[j][0]]+1) ;
代码:
class Solution {
public int videoStitching(int[][] clips, int T) {
int[] dp = new int[T+1]; //dp[i]表示覆盖[0,i]所需的最小片段
Arrays.fill(dp,Integer.MAX_VALUE-1); //下面会执行+1操作,故要max-1,否则会溢出
dp[0] = 0;
for(int i = 1;i<=T;i++){
for(int j=0;j<clips.length;j++){
if(clips[j][0]<i&&clips[j][1]>=i){ //j片段包含i
dp[i] = Math.min(dp[i],dp[clips[j][0]]+1) ;
}
}
}
return dp[T]==Integer.MAX_VALUE-1?-1:dp[T];
}
}

解法二:贪心
思路:每次找能包括起点,且结束点是最大的那个作为下一个片段
class Solution {
public int videoStitching(int[][] clips, int T) {
int start = 0;
boolean haveStart = false;
int maxEnd = Integer.MIN_VALUE;
int count = 0;
while(start<T){
for(int i=0;i<clips.length;i++){
if(clips[i][0]<=start&&clips[i][1]>start){
maxEnd = Math.max(maxEnd,clips[i][1]); //每次选结尾时间最大的
haveStart = true;
}
}
if(!haveStart){
return -1;
}
count++;
start = maxEnd; //让下一次的起点等于这一次的最大终点
maxEnd = Integer.MIN_VALUE;
haveStart = false;
}
return count;
}
}

1024. 视频拼接

原文:https://www.cnblogs.com/nickyBlog/p/13999055.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!