南昌建站推广公司,电商网站网络服务,免费网页制作成app,崇信县门户网站官网你将会获得一系列视频片段#xff0c;这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠#xff0c;也可能长度不一。
视频片段 clips[i] 都用区间进行表示#xff1a;开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠也可能长度不一。
视频片段 clips[i] 都用区间进行表示开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑例如片段 [0, 7] 可以剪切成 [0, 1] [1, 3] [3, 7] 三部分。
我们需要将这些片段进行再剪辑并将剪辑后的内容拼接成覆盖整个运动过程的片段[0, T]。返回所需片段的最小数目如果无法完成该任务则返回 -1 。
示例 1
输入clips [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T 10 输出3 解释 我们选中 [0,2], [8,10], [1,9] 这三个片段。 然后按下面的方案重制比赛片段 将 [1,9] 再剪辑为 [1,2] [2,8] [8,9] 。 现在我们手上有 [0,2] [2,8] [8,10]而这些涵盖了整场比赛 [0, 10]。
dp代码
class Solution {public int videoStitching(int[][] clips, int T) {int[] dpnew int[T1];Arrays.fill(dp,1000);dp[0]0;for(int i1;iT;i){for(int[] c:clips)//遍历可选片段if(i-c[0]0c[1]i)//满足c【0】ic[1]才可以选当前片段 dp[i]Math.min(dp[i],dp[c[0]]1);
//Math.min(c【0】之前最优解1选择当前剪辑时间当前位置的最优解}return dp[T]1000?-1:dp[T];}
}贪心代码 public int videoStitching(int[][] clips, int T) {int[] dpnew int[T];for(int[] c:clips){if(c[0]T)dp[c[0]] Math.max(dp[c[0]],c[1]);}int pre0,last0,res0;for(int i0;iT;i){lastMath.max(last,dp[i]);if(ilast)return -1;if(ipre){res;prelast;}}return res;}
