视频拼接

描述

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

使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。

甚至可以对这些片段自由地再剪辑：

• 例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

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

示例

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出：3
解释：
选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。

题解

function videoStitching(clips: number[][], time: number): number {
  // 将输入数据整理，起始位置作为下标，步长作值
  const nums = new Array(time).fill(0);
  for (const [i, j] of clips) {
    if (nums[i] < time) {
      nums[i] = Math.max(nums[i], j - i);
    }
  }
  console.log(nums);
  // 总数
  let res = 0;
  // 下一步的最长距离
  let next = 0;
  // 当前的最长距离
  let cur = 0;
  // 遍历数组
  for (let i = 0; i < time; i++) {
    // 大于当前最大的步长，不能正确截取
    if (i > cur) return -1;
    // 下一步的最大值
    next = Math.max(next, nums[i] + i);
    // 起始位置等于当前最大步长
    if (i === cur) {
      cur = next;
      res++;
    }
  }
  // 当前能到达的最远距离大于等于总距离，返回结果
  return cur >= time ? res : -1;
}