1024.视频拼接

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

题解 1 - typescript

• 编辑时间：2020-10-24
• 执行用时：100ms
• 内存消耗：40.6MB
• 编程语言：typescript
• 解法介绍：[参考连接](https://leetcode-cn.com/problems/video-stitching/solution/shi-pin-pin-jie-by-leetcode-solution/)。

function videoStitching(clips: number[][], T: number): number {
  const dp = new Array(T + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i <= T; i++) {
    for (const clip of clips) {
      if (clip[0] < i && i <= clip[1]) {
        dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
      }
    }
  }
  return dp[T] === Infinity ? -1 : dp[T];
}