LEETCODE 1024. Video Stitching 解题思路分析

题目大意：

视频拼接

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

视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1024

解题思路分析：

这道题我使用的贪心算法，所谓贪心，就是每次尽可能的找到当前最好的结果。比如我们当前的片段为[0, 5]，那么下一片段在保证与当前有交集的前提下，尽量覆盖到更远的范围。比如，[4, 6]和[1, 10]，显然后者是更好的结果。具体思路为：

1. 首先先遍历出，以所有起点开始，能够覆盖到的最大距离，比如有[0, 5]和[0, 10]，那么[0, 10]是最优解，就是说从0开始能够覆盖的最大距离为10。
2. 当得知每个点能够覆盖的最大距离之后，从0这个起点开始循环，先看0能够覆盖到的最远距离，我们称之为currendEnd。然后在1到currendEnd范围内查看他们能覆盖到的最远距离nextMaxEnd是多少，如果nextMaxEnd小于等于currendEnd，说明0到其能覆盖范围内的所有起点都无法跨越0至currendEnd的距离，也就无法将后面的片段连接起来，直接返回false。反之，如果nextMaxEnd大于currendEnd，说明我们已经可以覆盖到更远的nextMaxEnd范围内，这时我们再从currendEnd与nextMaxEnd之间寻找后面更远的覆盖范围，直到nextMaxEnd大于等于目标T为止。总共寻找的次数就是最终结果。

看下实现代码：

public int videoStitching(int[][] clips, int T) {
    int[] rangeMap = new int[T + 1]; // 用于存储每个起点能覆盖到的最大范围
    for (int[] clip : clips) {
        if (clip[0] > T) {
            continue;
        }
        rangeMap[clip[0]] = Math.max(rangeMap[clip[0]], clip[1]);
    }
    // 从0开始，看其最远覆盖范围是多少。
    int currendEnd = rangeMap[0];
    // 返回结果，将0计入次数中，所以初始值为1
    int res = 1;
    // 因为0已经预先定义好，所以从1开始循环
    int i = 1;
    // 当currendEnd 大于等于目标值T时，结束循环
    while (currendEnd < T) {
        // 定义下一个最远覆盖范围
        int nextMaxEnd = 0;
        // 从当前位置到currendEnd范围内的所有数为起点，找其能覆盖的最远距离
        for (int j = i; j <= currendEnd; j++) {
            nextMaxEnd = Math.max(nextMaxEnd, rangeMap[j]);
        }
        // 如果找到的最远距离无法超越currendEnd，说明后续片段无法连接
        if (nextMaxEnd <= currendEnd) {
            return -1;
        }
        // 将i至于currendEnd之后
        i = currendEnd + 1;
        // 当前能覆盖的最远距离更新为nextMaxEnd
        currendEnd = nextMaxEnd;
        // 次数加一
        res++;
    }
    return res;
}

本解法用时0ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1024-video-stitching-解题思路分析/