LeetCode 1024. 视频拼接

2024-01-29 HGNULB 约 9 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1024. 视频拼接

题意分析

手上有一堆片段，每个片段是一段闭区间 [start, end]，可以随意挑选、允许重叠、允许不用。目标是让选中片段的并集完整盖住 [0, time]，并且用的片段数最少；盖不住就返回 -1。

有几个约束信号值得注意。第一，片段可以任意重叠，说明这不是「选出互不相交的一组」，而是「用尽量少的块铺满一条线段」，重叠是允许甚至必要的代价。第二，片段没有排序保证，起点终点都可能乱序，所以直接线性扫描原数组得不到有意义的推进顺序。第三，time 与坐标的上界都不大（百量级），既容忍 $O(n \log n)$ 也容忍按时间轴逐点处理。

边界要想清楚三处：time 为 0 时什么都不用选，答案是 0；没有任何片段以 0 为起点（或起点全部大于 0）时立刻无解；覆盖到中途出现空隙，比如手上片段最远只到 5 而下一个片段从 6 开始，中间那个点没人盖，同样无解。注意区间是闭的，恰好首尾相接的两段 [0,5] 和 [5,9] 是能拼上的。

解法：排序后贪心扩展最远覆盖

核心思路

先想暴力：设 dp[i] 为盖住 [0, i] 所需的最少片段数，对每个 i 枚举所有片段，若某片段 [s, e] 满足 s < i <= e，就用 dp[s] + 1 更新 dp[i]。这是对的，代价是 $O(n \cdot time)$。瓶颈在于，每个位置都把全部片段重新扫了一遍，而绝大多数片段在那一刻根本不可能被选中。

观察一下最优解长什么样。把选中的片段按起点排好，它们必然形成一条链：第一段必须从 0 或更左开始，后一段的起点必须落在前面已覆盖的范围内，否则中间断开。既然是链，就可以一节一节地定：已经确定了前 k 段、覆盖到位置 curEnd，那么第 k+1 段只能从「起点不超过 curEnd」的片段里挑。

关键的交换论证是：在这批候选里挑终点最远的那个绝不会更差。假设最优解在这一步选了终点较近的片段，把它换成终点最远的那个，覆盖范围只增不减，后续所有可选片段的集合只会变大，因此片段总数不会增加。

不变量：进入每轮循环时，curEnd 是「用 ans 个片段能覆盖到的最远位置」，且区间 [0, curEnd] 已被完整覆盖；nextEnd 是「所有起点不超过 curEnd 的片段中最大的终点」。每轮把 curEnd 推进到 nextEnd 并令 ans 加一，直到 curEnd >= time。若某轮 nextEnd 等于 curEnd，说明可用片段全都无法越过 curEnd，出现断层，无解。

解题步骤

把 clips 按起点升序排序，起点相同时按终点降序。升序是为了让「起点不超过 curEnd」的片段总是排在数组前缀里，从而能用一个只增不减的指针 idx 扫过去；终点降序只是让同起点中更优的排在前面，对正确性没有影响，但便于调试观察。

初始化 curEnd = 0、nextEnd = 0、ans = 0、idx = 0。curEnd 从 0 起步隐含了「位置 0 这个点本身不需要被谁盖住，真正要盖的是 (0, time]」这一理解，也正因如此，只有终点严格大于 0 的片段才算有推进力。

外层循环条件是 curEnd < time：还没盖到终点就继续选片段。

内层把所有 clips[idx][0] <= curEnd 的片段吃掉，用它们的终点更新 nextEnd。idx 全程不回退，因为一旦某个片段的起点满足了当前的 curEnd，它对以后更大的 curEnd 也一定满足，重复检查纯属浪费。

内层结束后若 nextEnd == curEnd，返回 -1。这一步同时覆盖了两种失败情形：一是根本没有片段能起步（curEnd 还是 0 而没人终点大于 0），二是中途出现空洞。

否则 ans 加一、curEnd = nextEnd，表示真正敲定了一个片段。累加必须放在内层扫描之后，因为一轮扫描对应的是「从若干候选里最终挑一个」，而不是扫到几个就用几个。

以 clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]、time = 10 走一遍：排序后数组变成 [0,2], [1,9], [1,5], [4,6], [5,9], [8,10]。初始 curEnd = 0、nextEnd = 0、ans = 0、idx = 0。第一轮，[0,2] 的起点 0 <= 0 被吃掉，nextEnd 变 2，idx 到 1；下一个起点是 1，大于 curEnd = 0，内层停。nextEnd = 2 不等于 0，于是 ans = 1、curEnd = 2。第二轮，[1,9] 起点 1 <= 2，nextEnd 更新为 9，idx 到 2；[1,5] 起点也满足，终点 5 小于 9 不更新，idx 到 3；[4,6] 起点 4 > 2，内层停。ans = 2、curEnd = 9。第三轮，[4,6] 起点 4 <= 9，终点 6 不更新，idx 到 4；[5,9] 终点 9 不更新，idx 到 5；[8,10] 起点 8 <= 9，nextEnd 更新为 10，idx 到 6 越界，内层停。ans = 3、curEnd = 10。此时 curEnd >= time，外层退出，返回 3，对应选中 [0,2]、[1,9]、[8,10]。

代码实现

class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });

        int ans = 0;
        int idx = 0;
        int curEnd = 0;
        int nextEnd = 0;

        while (curEnd < time) {
            // 在当前可覆盖范围内，挑出能把右边界推得最远的片段。
            while (idx < clips.length && clips[idx][0] <= curEnd) {
                nextEnd = Math.max(nextEnd, clips[idx][1]);
                idx++;
            }

            if (nextEnd == curEnd) {
                return -1;
            }

            ans++;
            curEnd = nextEnd;
        }

        return ans;
    }
}

func videoStitching(clips [][]int, time int) int {
    sort.Slice(clips, func(i, j int) bool {
        if clips[i][0] != clips[j][0] {
            return clips[i][0] < clips[j][0]
        }
        return clips[i][1] > clips[j][1]
    })

    ans := 0
    idx := 0
    curEnd := 0
    nextEnd := 0

    for curEnd < time {
        // 在当前可覆盖范围内，挑出能把右边界推得最远的片段。
        for idx < len(clips) && clips[idx][0] <= curEnd {
            if clips[idx][1] > nextEnd {
                nextEnd = clips[idx][1]
            }
            idx++
        }

        if nextEnd == curEnd {
            return -1
        }

        ans++
        curEnd = nextEnd
    }

    return ans
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 是片段数。排序是主导项；主体的双层循环里 idx 单调递增且永不回退，所有内层迭代加起来只有 $O(n)$ 次，外层轮数不超过 $n$。

空间复杂度：贪心扫描本身是 $O(1)$；计入标准库排序后，Java 对 int[][] 这种对象数组排序最坏需要 $O(n)$ 辅助空间，Go 的原地内省排序需要 $O(\log n)$ 调用栈。

关键点总结

区间覆盖类贪心的模板是「双边界」：一个记录已经兑现的覆盖终点，一个记录当前候选能达到的最远终点，两者相等即为断层信号。这套结构可以原样迁移到跳跃游戏系列。

贪心成立与否要靠交换论证支撑，而不是靠直觉。这里的论证是「把最优解中的某一段替换成同批候选里终点最远的那段，覆盖范围单调不减」，能说清这句话，面试里的正确性质疑就化解了。

排序 + 单调指针的组合是消除重复扫描的常用手段。判断指针能否不回退，标准是「条件一旦满足就永远满足」，这里因为 curEnd 单调不减，所以成立。

闭区间的首尾相接算连通，开区间不算。动手前先确认区间语义，能避免大量边界纠纷。

面试视角：先给出 $O(n \cdot time)$ 的动态规划，再说明它的浪费在哪，最后升级到贪心，是这题的标准展示路线。如果面试官把坐标范围放大到 $10^9$，动态规划直接失效，贪心却仍然可行，这一点值得主动点出来。

面试视角：常见追问是「为什么不按终点排序」。按终点排序会丢掉「起点必须落在已覆盖范围内」这个约束的检查时机，导致选出的片段之间可能断开，可以现场举反例说明。

易错点总结

错误写法：把 ans++ 写进内层循环，扫到一个满足条件的片段就计一次数。用例 [[0,2],[1,9],[1,5]]、time = 9 → 一轮里吃掉三个片段就加了三次，返回 4 而正确答案是 2。

错误写法：内层条件写成 clips[idx][0] < curEnd。用例 [[0,5],[5,9]]、time = 9 → 起点恰好等于 curEnd = 5 的片段被排除，判定为断层返回 -1，而闭区间下这两段是能接上的。

错误写法：断层判断写成 if (nextEnd <= curEnd) 之外的形式，比如漏掉这个判断直接推进。用例 [[0,1],[6,8]]、time = 8 → 第二轮 nextEnd 仍是 1，curEnd 原地不动，外层条件永远为真，陷入死循环。

错误写法：外层循环条件写成 curEnd <= time。用例 [[0,4],[2,8]]、time = 8 → 覆盖到 8 后仍要再进一轮，此时已无片段可推进，误返回 -1。

错误写法：每轮把 nextEnd 重置为 0 或重置为 curEnd 之后又不重新扫描已越过的片段。用例 [[0,2],[1,9],[3,4]]、time = 9 → 之前累积的最远终点被抹掉，后面又因 idx 不回退取不到，结果误判无解。

错误写法：不排序直接按原顺序用单调指针扫描。用例 [[1,5],[0,2],[4,6],[8,10],[1,9],[5,9]]、time = 10 → 第一轮遇到起点为 1 的片段就停下，起点为 0 的片段被永久跳过，直接返回 -1。

错误写法：认为「片段越长越好」，先按长度降序排序再依次贪心取。用例 [[0,1],[1,9],[0,8]]、time = 9 → 先取最长的 [1,9] 会让位置 0 到 1 这段无人覆盖，被迫多用片段甚至误判无解。

错误写法：忽略 time 为 0 的情形，在循环外无条件写 ans = 1。用例任意片段、time = 0 → 返回 1，而正确答案是不选任何片段的 0。

错误写法：把 idx 每轮重置为 0。用例片段数较多时 → 结果仍然正确，但复杂度退化成 $O(n^2)$，在面试里会被追问为什么不用单调指针。

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	同样的双边界贪心，区间由下标与步长隐式给出
55. 跳跃游戏	中等	只判可达性，无需统计使用次数
435. 无重叠区间	中等	目标是保留最多互不相交的区间，按终点排序
452. 用最少数量的箭引爆气球	中等	求区间的最少公共点数，用重叠交集收缩
1288. 删除被覆盖区间	中等	判定包含关系并计数，重点在同起点的排序技巧
757. 设置交集大小至少为2	困难	每个区间需贡献两个点，贪心需回看已选点