1024. 视频拼接

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

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

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

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

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

示例 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]。

示例 2：

输入：clips = [[0,1],[1,2]], time = 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]], time = 9
输出：3
解释： 
选取片段 [0,4], [4,7] 和 [6,9] 。

提示：

• 1 <= clips.length <= 100
• 0 <= starti <= endi <= 100
• 1 <= time <= 100

类似跳跃游戏II

动态规划，背包问题

先遍历容量，再遍历物品时不需要排序，因为dp[i]依赖于dp[j]（j<i），而我们是先计算的小容量的结果，再计算大容量的结果。所以不需要排序。

先遍历物品，再遍历容量时需要排序，因为如果不对视频片段进行排序的话，我们固定一个视频片段后，在该区间内的时间点有可能很靠后， 我们需要先计算前面的时间点，才能计算后面的时间点。

class Solution {
    public int videoStitching(int[][] clips, int time) {
        // 创建一个dp数组，dp[i]表示拼接到时间i所需的最少片段数
        int[] dp = new int[time + 1];
        // 初始化dp数组，因为我们要求最小值，所以每个元素都设置为一个较大的数（MAX_VALUE - 1），表示初始化状态
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        // 拼接到时间0所需的片段数为0，因为不需要任何片段，表示0秒。
        dp[0] = 0;
        // 遍历从1到time的每个时间点
        for (int i = 1; i <= time; i++) {
            // 遍历所有的视频片段
            for (int[] clip : clips) {
                // 如果当前时间点i在视频片段clip的时间范围内（clip[0] < i <= clip[1]），即能够覆盖当前时间点。注意大于号和大于等于号。
                if (clip[0] < i && i <= clip[1]) {
                    // 更新dp[i]，取当前dp[i]和dp[clip[0]] + 1的最小值
                    dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                }
            }
        }

        // 如果dp[time]仍然是初始化的较大值，说明无法拼接成连续视频，返回-1
        // 否则返回拼接到time所需的最少片段数
        return dp[time] == Integer.MAX_VALUE - 1 ? -1 : dp[time];
    }
}

先遍历物品，再遍历容量：

class Solution {
    public int videoStitching(int[][] clips, int time) {
        // 按 clip[0] 升序排序视频片段。重点。
        Arrays.sort(clips, (a, b) -> a[0] - b[0]);
        
        // 创建一个 dp 数组，dp[i] 表示拼接到时间 i 所需的最少片段数
        int[] dp = new int[time + 1];
        // 初始化 dp 数组为一个较大值（MAX_VALUE - 1）
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        // 拼接到时间 0 所需片段数为 0
        dp[0] = 0;
        
        // 遍历所有视频片段
        for (int[] clip : clips) {
            int start = clip[0];
            int end = clip[1];
            // 遍历 clip 覆盖的时间点 i（start < i <= end 且 i <= time）
            for (int i = start + 1; i <= end && i <= time; i++) {
                // 更新 dp[i]，取当前 dp[i] 和 dp[start] + 1 的最小值
                dp[i] = Math.min(dp[i], dp[start] + 1);
            }
        }
        
        // 如果 dp[time] 未被更新，说明无法拼接，返回 -1；否则返回结果
        return dp[time] == Integer.MAX_VALUE - 1 ? -1 : dp[time];
    }
}

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

贪心-按起点升序排列，起点相同的降序排列。

分类：每次找到包含当前时间点的片段的最远结束时间。

import java.util.Arrays;

class Solution {
    public int videoStitching(int[][] clips, int T) {
        // 特殊情况处理：如果目标时间为0，不需要任何视频片段
        if (T == 0) return 0;

        // 将所有视频片段按开始时间升序排列；如果开始时间相同，则按结束时间降序排列
        Arrays.sort(clips, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1]; // 开始时间相同，按结束时间降序。其实不按结束时间降序排序也行。
            }
            return a[0] - b[0]; // 否则按开始时间升序
        });

        int res = 0; // 记录选择的短视频个数
        int curEnd = 0; // 当前覆盖的最远结束时间
        int nextEnd = 0; // 选择下一个视频后能达到的最远结束时间
        
        int i = 0; // 当前考察的视频片段索引
        int n = clips.length; // 视频片段的总数

        // 遍历所有视频片段
        while (i < n && clips[i][0] <= curEnd) {
            // 在当前区间内贪心选择可以达到的最远结束时间。其实没必要按终点降序排序，因为while是遍历所有clips并取最大值。
            // 起点小于等于curEnd才能保证连续。确保连续后，再找最远的终点。
            while (i < n && clips[i][0] <= curEnd) {
                // 选择之前先准备下一个最远可达的结束时间
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++; // 检查下一个片段
            }
            
            // 选择一个视频片段，并将当前结束时间更新为 nextEnd
            res++;
            curEnd = nextEnd;
            
            // 如果当前结束时间已经覆盖到目标时间 T，返回使用的片段数
            if (curEnd >= T) {
                return res;
            }
        }

        // 如果没有找到连续的视频片段覆盖到时间 T，返回 -1
        return -1;
    }
}

这段代码的时间复杂度是多少呢？虽然代码中有一个嵌套的 while 循环，但这个嵌套 while 循环的时间复杂度是 O(N)。 因为当 i 递增到 n 时循环就会结束，所以这段代码只会执行 O(N) 次。

但是别忘了我们对 clips 数组进行了一次排序，消耗了 O(NlogN) 的时间，所以本算法的总时间复杂度是 O(NlogN)。