leetcode1024

问题

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

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

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

solution

• 标准的贪心问题
• 先对时间片段进行排序（开始时间，结束时间）：可以想象为一个平行的时间轴，每一个时刻可能包含了多个时间轴，每个时刻都遍历这些时间轴，存下最小的时间片段数量。
• DP[T] 表示 $0-T$ 时刻的最小时间片段
• DP[T] = min(DP[T],DP[clip[0]]+1)

class Solution(object):
    def videoStitching(self, clips, T):

        clips.sort()
        DP = [T+1]*(T+1)
        DP[0] = 0
        for t in range(1,T+1):
            for clip in clips:
                if t>=clip[0] and t<=clip[1]:
                    DP[t] = min(DP[t],DP[clip[0]]+1)
        if DP[T]==T+1:
            return -1
        return DP[T]
        

最后

以上就是稳重蜜蜂为你收集整理的leetcode1024的全部内容，希望文章能够帮你解决leetcode1024所遇到的程序开发问题。

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