视频拼接

难度: Medium

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

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

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

例如，片段 [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 <= start_i <= end_i <= 100
1 <= time <= 100

Submission

运行时间: 25 ms

内存: 16.1 MB

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        maxn = [0] * time
        last = ret = pre = 0
        for a, b in clips:
            if a < time:
                maxn[a] = max(maxn[a], b)
        
        for i in range(time):
            last = max(last, maxn[i])
            if i == last:
                return -1
            if i == pre:
                ret += 1
                pre = last
        
        return ret

Explain

该题解采用的是贪心算法。首先，创建一个数组maxn，长度为time，用于记录每个时间点可以达到的最远结束时间。遍历输入的视频片段，如果片段的开始时间小于time，更新maxn数组中对应开始时间的位置为当前片段的结束时间和原有值的较大者。接着，遍历从0到time的时间点，使用变量last记录当前能到达的最远时间，pre记录前一个被选择的片段的结束时间，ret记录需要的片段数量。如果当前时间点i等于last，说明无法继续向前，返回-1表示不能覆盖整个时间段。如果i等于pre，说明需要选择一个新的片段，增加ret并更新pre为last。最后返回ret作为结果。

时间复杂度: O(n + time)

空间复杂度: O(time)

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        maxn = [0] * time  # 初始化maxn数组，长度为time
        last = ret = pre = 0  # 初始化last、ret、pre
        for a, b in clips:
            if a < time:  # 只考虑开始时间小于time的片段
                maxn[a] = max(maxn[a], b)  # 更新maxn中对应位置的最大结束时间
        
        for i in range(time):
            last = max(last, maxn[i])  # 更新能达到的最远时间
            if i == last:  # 如果当前时间等于last，说明无法进一步向前
                return -1
            if i == pre:  # 如果当前时间达到了上一个片段的结束时间
                ret += 1  # 需要新的片段
                pre = last  # 更新pre为当前的last
        
        return ret  # 返回所需的最小片段数

Explore

在算法中，如果`maxn`数组的某个位置值未被更新，即该位置的值仍为0，这意味着从该时间点开始没有任何视频片段。这将直接影响算法的执行流程和输出结果。具体地，当遍历到这个时间点时，由于没有可用的片段延伸覆盖范围，变量`last`（表示当前能到达的最远时间）不会增加，从而可能导致在这一时间点时`i`等于`last`。根据算法逻辑，这种情况下算法将返回-1，表示无法覆盖整个0到time的时间段，因此无法完成视频拼接任务。

算法通过检查是否存在片段从时间0开始的情况来处理视频片段完全不覆盖`[0, time]`区间的情况。特别地，如果在遍历过程中在时间0的位置`maxn[0]`值为0，这意味着没有任何视频片段开始于时间0。在这种情况下，变量`last`将一直保持为0，导致在第一次迭代时`i`将等于`last`。根据算法的设计，这将直接触发返回-1的条件，表明算法无法从0开始覆盖任何部分的时间段。因此，-1作为特殊的返回值，用于表示视频片段无法覆盖整个所需的时间段。