视频拼接如何用贪心覆盖目标区间？为什么每轮选能延伸最远的片段？

简化版

视频拼接是覆盖 [0,time] 的最少区间数。按起点排序后，从当前已覆盖右边界 curEnd 出发，在所有 start <= curEnd 的片段中选择能延伸到最远的 nextEnd。每选择一轮，片段数加 1；如果无法延伸，则失败。

详细版

这个题和跳跃游戏 II 很像：当前覆盖范围内的所有片段都是这一轮可选候选，我们要选一个让下一轮覆盖最远的。排序后用指针扫描所有起点不超过 curEnd 的片段，更新 nextEnd。一轮扫描结束后，如果 nextEnd == curEnd，说明出现断档，返回 -1。

时间复杂度 O(n log n)，空间复杂度取决于排序。也可以用数组预处理每个起点能到达的最远终点。

完整版教学

一、题目本质是最少区间覆盖

给一堆视频片段 [start,end]，要求拼出完整的 [0,time]。片段可以裁剪，所以只要覆盖连续时间线即可。

目标：[0,10]
片段：[0,3], [2,6], [6,10]

如果某个时间点没有任何片段覆盖，拼接就失败。

二、为什么每轮选延伸最远的片段

当当前已经覆盖到 curEnd，所有 start <= curEnd 的片段都能接上当前覆盖。为了减少总片段数，应该让下一次覆盖边界尽量远。

候选片段	是否能接上	延伸效果
`[1,4]`	能	到 4
`[2,8]`	能	到 8
`[5,9]`	不能	起点超过当前覆盖

记忆钩子：区间覆盖每一轮不是选最短，而是选当前能接上的最远右端。

这和跳跃游戏里“当前步数范围内选下一步能到最远”完全一致。

三、排序后扫描怎么组织

先按起点升序排序。维护：

curEnd = 当前已经确定覆盖到哪里
nextEnd = 本轮候选能延伸到的最远位置

扫描所有 clips[i][0] <= curEnd 的片段，更新 nextEnd=max(nextEnd, clips[i][1])。扫描完一轮后，必须使用一个片段，所以答案加 1，并令 curEnd=nextEnd。

四、断档条件是什么

如果一轮扫描后 nextEnd == curEnd，说明所有能接上的片段都无法让覆盖继续向右扩展。

已覆盖到 4
下一个片段最早从 6 开始
时间 4..6 断档

此时无论怎么选都无法覆盖完整目标，返回 -1。

五、代码模板

int videoStitching(int[][] clips, int time) {
    Arrays.sort(clips, Comparator.comparingInt(a -> a[0]));
    int ans = 0, curEnd = 0, nextEnd = 0, i = 0;
    while (curEnd < time) {
        while (i < clips.length && clips[i][0] <= curEnd) {
            nextEnd = Math.max(nextEnd, clips[i][1]);
            i++;
        }
        if (nextEnd == curEnd) return -1;
        ans++;
        curEnd = nextEnd;
    }
    return ans;
}

注意外层循环条件是 curEnd < time。一旦覆盖边界达到或超过 time，就完成了。

六、用例子推演

clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]，time=10。

curEnd=0：可选 [0,2]，nextEnd=2，ans=1
curEnd=2：可选 [1,9],[1,5]，nextEnd=9，ans=2
curEnd=9：可选 [4,6],[5,9],[8,10]，nextEnd=10，ans=3

答案是 3。中间选 [1,9] 的原因是它在当前可接片段里延伸最远。

七、常见误区与追问

误区：每次选当前最短片段。 最短片段可能导致片段数变多，目标是最少数量。
误区：只看起点最早的片段。 起点能接上即可，关键是右端延伸多远。
误区：断档时继续扫描后面片段。 后面片段起点更大，已经接不上当前覆盖。
追问：为什么和跳跃游戏 II 类似？ 当前覆盖范围像当前步可达范围，nextEnd 是下一步最远可达。
追问：片段可裁剪有什么影响？ 只要覆盖时间线即可，不要求片段完整使用。
追问：复杂度是多少？ 排序 O(n log n)，扫描 O(n)。

八、加强记忆

视频拼接就是“用最少区间盖住 [0,time]”。每轮从已覆盖边界出发，把所有能接上的片段看一遍，选右端最远的那个效果；如果本轮无法把边界推远，就是断档。它的思维和跳跃游戏 II 同源：一层一层扩展覆盖范围。

简化版

详细版