leetcode第1024题视频拼接

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/video-stitching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：动态规划

• 首先找到最后一个状态，也就是覆盖0~i所需要的最小片段数
• 对于任意一个片段有两周可能选择或者不选择
• 选择的条件是 当前所计算的值可以覆盖该片段的左区间
• 如果当前片段可以被选择，就判断选择这个片段是不是可以让覆盖0~i的片段数更小，如果是的话就更新dp[i]的值
• 如果dp[time]被覆盖了，那就说明能够包含time

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        int n=clips.size();
        //dp[i]=0-i区间的最小片段
        vector<int> dp(time+1,INT_MAX-1);
        dp[0]=0;
        for(int i=1;i<=time;i++)
        {
            for(int j=0;j<n;j++)
            {
                //其实对于每一个片段，都有两种情况，选或者不选，如果已经计算的能到达的时间包含在这一个片段内，就可以用这个片段
                
                if(clips[j][0]<i&&clips[j][1]>=i)
                //至于是否选择，那就是看加入这个片段，是否可以让0~i区间的片段更小
                //dp[clips[j][0]]=0~clips[j][0]的最小片段数，也就是到达当前片段左边界值的最小片段数
                    dp[i]=min(dp[i],dp[clips[j][0]]+1);
            }
        }
        //如果最后的值没有更新的话，说明到不了time这个时间点，那就返回-1
        if(dp[time]==INT_MAX-1)
            return -1;
        return dp[time];
    }
};

最后

以上就是文静溪流为你收集整理的leetcode第1024题视频拼接leetcode第1024题视频拼接的全部内容，希望文章能够帮你解决leetcode第1024题视频拼接leetcode第1024题视频拼接所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。