LeetCode-1024. 视频拼接

问题地址

LeetCode每日一题/2020-10-24

LeetCode1024. 视频拼接

问题描述

规则

你将会获得一系列视频片段，这些片段来自于一项持续时长为 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]。

• 示例2

输入：clips = [[0,1],[1,2]], T = 5
输出：-1
解释：
我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

• 示例3

输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
输出：3
解释： 
我们选取片段 [0,4], [4,7] 和 [6,9] 。

• 示例4

输入：clips = [[0,4],[2,8]], T = 5
输出：2
解释：
注意，你可能录制超过比赛结束时间的视频。

进阶

• 1 <= clips.length <= 100
• 0 <= clips[i][0] <= clips[i][1] <= 100
• 0 <= T <= 100

思路分析

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

官方解法

前言

本题要求从一系列视频子区间中选出尽可能少的一部分，使得这部分视频子区间能够重新剪出一个完整的视频。我们可以这样理解：给定区间 [0,T) 的一系列子区间（可能重叠），要求从中选出尽可能少的子区间，使得这些子区间能够完全覆盖区间 [0,T)。

为下文表述方便，我们用 [a,b) 来代表每一个子区间，第 i 个子区间表示为 [a_i,b_i)。

方法一 动态规划

思路及算法

• 比较容易想到的方法是动态规划，我们令 \textit{dp}[i] 表示将区间 [0,i) 覆盖所需的最少子区间的数量。由于我们希望子区间的数目尽可能少，因此可以将所有 \textit{dp}[i] 的初始值设为一个大整数，并将 \textit{dp}[0]（即空区间）的初始值设为 0。

• 我们可以枚举所有的子区间来依次计算出所有的 \textit{dp} 值。我们首先枚举 i，同时对于任意一个子区间 [a_j,b_j)，若其满足d： a_j < i ≤ b_j 。

• 那么它就可以覆盖区间 [0, i) 的后半部分，而前半部分则可以用 \textit{dp}[a_j] 对应的最优方法进行覆盖，因此我们可以用 dp[a_j] + 1 来更新 \textit{dp}[i]。状态转移方程如下：dp[i] = \min{dp[a_j]}+ 1

• 最终的答案即为 \textit{dp}[T]。

复杂度分析：

1. 时间复杂度:O(T×N)，其中 T 是区间的长度，N 是子区间的数量。对于任意一个前缀区间 [0,i) ，我们都需要枚举所有的子区间，时间复杂度 O(N)。总时间复杂度为 O(T) \times O(N) = O(T \times N)。
2. 空间复杂度：O(T)，其中 T 是区间的长度。我们需要记录每一个前缀区间 [0,i) 的状态信息。

编码实现

class Solution {
    public int videoStitching(int[][] clips, int T) {
        int[] dp = new int[T + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        for (int i = 1; i <= T; i++) {
            for (int[] clip : clips) {
                if (clip[0] < i && i <= clip[1]) {
                    dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                }
            }
        }
        return dp[T] == Integer.MAX_VALUE - 1 ? -1 : dp[T];
    }
}

方法二 贪心

思路

• 注意到对于所有左端点相同的子区间，其右端点越远越有利。且最佳方案中不可能出现两个左端点相同的子区间。于是我们预处理所有的子区间，对于每一个位置 i，我们记录以其为左端点的子区间中最远的右端点，记为 \textit{maxn}[i]。
• 我们可以参考「55. 跳跃游戏的官方题解」，使用贪心解决这道题。
• 具体地，我们枚举每一个位置，假设当枚举到位置 i 时，记左端点不大于 i 的所有子区间的最远右端点为 \textit{last}。这样 \textit{last} 就代表了当前能覆盖到的最远的右端点。
• 每次我们枚举到一个新位置，我们都用 \textit{maxn}[i] 来更新 \textit{last}。如果更新后 last == ilast==i，那么说明下一个位置无法被覆盖，我们无法完成目标。
• 同时我们还需要记录上一个被使用的子区间的结束位置为 \textit{pre}，每次我们越过一个被使用的子区间，就说明我们要启用一个新子区间，这个新子区间的结束位置即为当前的 \textit{last}。也就是说，每次我们遇到 i == pre，则说明我们用完了一个被使用的子区间。这种情况下我们让答案加 1，并更新 \textit{pre} 即可。

复杂度分析：

1. 时间复杂度:O(T+N)，其中 T 是区间的长度，N 是子区间的数量。我们都需要枚举每一个位置，时间复杂度 O(T)。总时间复杂度为 O(T) + O(N) = O(T + N)。

2. 空间复杂度：O(T)，其中 T 是区间的长度。我们需要记录以其为左端点的子区间的最右端点。

编码实现

class Solution {
    public int videoStitching(int[][] clips, int T) {
        int[] maxn = new int[T];
        int last = 0, ret = 0, pre = 0;
        for (int[] clip : clips) {
            if (clip[0] < T) {
                maxn[clip[0]] = Math.max(maxn[clip[0]], clip[1]);
            }
        }
        for (int i = 0; i < T; i++) {
            last = Math.max(last, maxn[i]);
            if (i == last) {
                return -1;
            }
            if (i == pre) {
                ret++;
                pre = last;
            }
        }
        return ret;
    }
}

精彩评论

跳转地址1：【Java】1024节，不准不“贪心”

思路

(本题解 借鉴了 官方题解 的思想)
– 很纯粹的 贪心 思想：
– 1、首先来初始化一个 maxEnd数组，用于保存 以当前数字(下标)为起点 的区间的 最大的结束位置
– 2、遍历clips，初始化maxEnd数组(每个元素开头的区间的最大结束位置)
– 3、定义三个变量，辅助完成之后的操作：
– 1、pre 记录 结果中上一次的最大结束位置(本轮的最小开始位置)
– 2、last 记录 当前遍历到的 区间最大结束位置
– 3、count 记录 结果
– 4、根据maxEnd数组，计算最终结果

• 因为maxEnd[i]数组为最大结束位置，因此：
  • 当前元素 == 本区间最大元素，即：区间断开，无法连续到后续位置，返回-1;
  • 当前元素 == 上一个区间的最大结束元素，即：到达了上一个满足条件的区间的结束位置
    这时的last为当前最大的结束位置，我们将其放入满足条件的区间集合之中(因为本题只需要我们记录 满足条件的区间个数，因为只需要 更新count和pre 即可)

编码实现

class Solution {
    public int videoStitching(int[][] clips, int T) {
        if (clips == null) {
            return 0;
        }

        int[] maxEnd = new int[T];  // 用于保存 以当前数字(下标)为起点 的区间的 最大的结束位置

        /*
            遍历clips，初始化maxEnd数组(每个元素开头的区间的最大结束位置)
         */
        for (int[] clip : clips) {
            if (clip[0] < T) {
                maxEnd[clip[0]] = Math.max(maxEnd[clip[0]], clip[1]);
            }
        }

        /*
            根据maxEnd数组，计算最终结果
                因为maxEnd[i]数组为最大结束位置，因此：
                    1、当前元素 == 本区间最大元素，
                        即：区间断开，无法连续到后续位置，返回-1
                    2、当前元素 == 上一个区间的最大结束元素，
                        即：到达了上一个满足条件的区间的结束位置
                        这时的last为当前最大的结束位置，我们将其放入满足条件的区间集合之中
                        (因为本题只需要我们记录 满足条件的区间个数，因为只需要 更新count和pre 即可)
         */
        int pre = 0;    // 记录 结果中上一次的最大结束位置(本轮的最小开始位置)
        int last = 0;   // 记录当前遍历到的 区间最大结束位置
        int count = 0; // 记录结果
        for (int i = 0; i < T; i++) {
            last = Math.max(maxEnd[i], last);
            if (i == last) {    // 当前元素 == 本区间最大元素(无法到达后续位置)
                return -1;
            }

            if (i == pre) { // 当前元素 == 上一个区间的最大元素
                count++;
                pre = last;
            }
        }
        return count;
    }
}
}

//反转链表
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

跳转地址2：「手画图解」动态规划 思路 | 分情况讨论

思路

题目要求覆盖[0,T]区间的最少片段数。

对于每个片段，用或不用，用就+1，且用过的片段，会影响之后对片段的选用，过去的状态影响当前状态，有 DP 的味道了。

尝试定义dp[j]，表示：覆盖[0,j]区间的最少片段数，题目是求dp[T]。

先将片段按开始时间从小到大排序，满足DP「顺序计算」的特点，先遍历“靠前”的片段。做什么事情呢？计算每个片段里的所有dp[j]。

从左到右求，有些dp[j]可能会重复求（如上图），求出值更小，就更新。最后求出dp[T]。

• 怎么求dp[j]？即，递推关系怎么找？我们画图看看，有哪些情况：
  • 情况1，覆盖不了[0:start]，也覆盖不了[0:j]，我们让dp[start]为一个很大的值，101，所有为101的 dp 结果都代表无法覆盖，返回 -1。此时dp[j]不小于 101 即可。
  • 情况2，覆盖[0:start]只要一个片段，覆盖[0:j]，一个片段不够，还要加上它所在的片段，有dp[j]=dp[start]+1。
  • 情况3，之前计算过dp[j]，再次计算，则要和之前的dp[j]比较，取较小者：dp[j]=min(dp[j], dp[start]+1)
    

回过头看情况1，dp[start]=101，我们希望dp[j]不小于101，且满足递推公式dp[j]=min(dp[j], dp[start]+1)，于是我们让所有dp[j]初始值为101。这是 base case 之一。

回过头看情况2，如下图，dp[start]其实求了两次，第一次dp[start]怎么求？同样为了套用dp[j]=min(dp[j], dp[start]+1)，让dp[0]=0，dp[start]初始为101，套公式为 min(101, 0+1)。

编码实现

递推公式有了，base case 有了，就可以写代码了。

const videoStitching = (clips, T) => {
  clips.sort((a, b) => a[0] - b[0]); // 按开始时间从小到大排序
  // dp[j]：涵盖[0:j]需要的clip的最少个数，目标是求dp[T]，初始值为101，大于所有可能值
  const dp = new Array(T + 1).fill(101);
  dp[0] = 0;        // base case

  for (let i = 0; i < clips.length; i++) { // 遍历每个片段
    const [start, end] = clips[i];         // 获取当前片段的开始和结束时间
    for (let j = start + 1; j <= end; j++) { // 计算当前片段上每个点的dp[j]
      dp[j] = Math.min(dp[j], dp[start] + 1);
    }
  }
  if (dp[T] == 101) { // 如果dp值为101，说明覆盖不了[0:T]，否则返回dp[T]
    return -1;
  }
  return dp[T];
};

总结复盘

动态规划顺序计算的特点决定了要排序。

过去的计算结果会影响到当前的计算，当前的计算，还受「当前所在片段的 start 的计算结果」的影响。

二者作用之下，写出递推公式（状态转移方程）。

然后 base case 基于公式往上套，让「边界情况也能套用上递推公式」而已。

大致的思路就是这样。

优化

当dp[start] = 101时，表示覆盖不了[0:start]，肯定覆盖不了[0,j]的，没必要遍历当前片段[start:end]上的所有j，直接 break：

const videoStitching = (clips, T) => {
  clips.sort((a, b) => a[0] - b[0]); // 按开始时间从小到大排序
  // dp[j]：涵盖[0:j]需要的clip的最少个数，目标是求dp[T]，初始值为101，大于所有可能值
  const dp = new Array(T + 1).fill(101);
  dp[0] = 0; // 涵盖[0:0]不需要clip，所以为0

  for (let i = 0; i < clips.length; i++) { // 遍历每个片段
    const [start, end] = clips[i];         // 获取当前片段的开始和结束时间
    if (dp[start] == 101) { // 该片段上都覆盖不了，直接退出循环，保持为101
      break;
    }
    for (let j = start + 1; j <= end; j++) { // 计算当前片段上每个点的dp[j]
      dp[j] = Math.min(dp[j], dp[start] + 1);
    }
  }

  if (dp[T] == 101) {
    return -1;
  }
  return dp[T];
};