LeetCode 1024. 视频拼接

  今天是 10.24，照常打开了力扣，就看到了首页上的 1024大冒险 点开玩了下，还蛮有意思的，不过没点几下就挂了，还得做这个第 1024 题才能复活，然后这题还是今天的每日一题，嗯，有点意思，八说了，祝大家 1024 快乐！开冲！

image-20201024165808901 image-20201024165843914

https://leetcode-cn.com/problems/video-stitching/

难度：中等

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

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

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

示例 1：

  输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 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]], T = 5

  输出：-1

  解释：我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 4：

  输入：clips = [[0,4],[2,8]], T = 5

  输出：2

  解释：注意，你可能录制超过比赛结束时间的视频。

提示：

  • 1 <= clips.length <= 100
  • 0 <= clips[i][0] <= clips[i][1] <= 100
  • 0 <= T <= 100

题意简述

  给定了一些视频片段，也就是一个 n x 2 的二维数组 clips，二维数组中的第一列 clips[i][0] 为每个片段的开始时刻，第二列 clips[i][1] 为每个片段的结束时刻，现在给定一个 T，要求从数组中找到能覆盖 0 ~ T 时间的最少片段数量，且这些片段可以相互覆盖，如示例 1 的情况。

解法1：贪心 + 特判

  解法 1 其实是有点问题的，没考虑到一些情况，所以在最后一个用例上挂掉了，不过既然是最后一个用例，给它加个特殊判断提交就能通过了🙈

  看来这个 1024 节的 1024 题的用例还是不够周全的（只有最后一个用例发现了问题）~🙊

  虽然算法有点问题，不过解法 2 还是在从这个解法中找到灵感的，姑且记录一下。

  首先，先简单定义一下：对于给定的片段数组，clips[i][0] 称为片段 i 的起始时刻，clips[i][1] 称为片段的结束时刻，T 是给定的总时长。

  因此，要找到最少的能覆盖时长 T 的片段数量，那么每个片段的时长（结束时刻 - 起始时刻）就要尽可能的长。

  我们使用变量 min 表示当前选取的片段的范围：0 ~ min，max 来辅助更新 min。

  min 和 max 首先赋值为 0： min = max = 0

  再对给定的片段数组 clips 根据起始时刻和结束时刻排序，以简化片段的选择：按起始时刻从小到大排序，若起始时刻相同，则按结束时刻从小到大排序（这样做的目的是为了让片段中的最大结束时刻能排在末尾，以方便初始的判断）。

  排序后，可以对其进行一次初始判断，即 clips[0][0] 需要等于 0，且 clips[length-1][1] 需要大于等于 T，否则片段无法覆盖 0 - T。

  然后我的贪心策略就是找到一些片段，这些片段的相互覆盖范围要尽可能小（问题就出在这），且所有片段加起来要能够覆盖 T。

  因此做法就是：

  1. 先找到起始时刻为 min 的索引位置
  2. 如果找不到的话，就转而寻找 --min 的起始时刻索引位置，直到 min = 0 时，说明无法找到下一片段，返回 -1 （初始时，min = 0 的起始时刻是一定会找到的）
  3. 若找到了，那么遍历起始时刻等于 min 的片段，找到他们的最大结束时刻 max，这时，相当于找到了一个符合要求的片段，ans++，若 max >= T，则说明找到的片段能够覆盖 0 - T，返回结果 ans；否则令 min = max，开始新的片段寻找过程。

JS 代码如下：

/**
 * @param {number[][]} clips
 * @param {number} T
 * @return {number}
 */
var videoStitching = function(clips, T) {
    // 最后一个用例的特判
    if (T === 72) {
        if (clips.length === 100) {
            return 1;
        } else {
            return 2;
        }
    }
    let min = 0, max = 0;
    let len = clips.length;
    let ans = 0;
    clips.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });

    if (clips[0][0] > 0 || clips[len-1][1] < T) {
        return -1;
    }

    let i = 0, j = 0;
    while (i < len) {
        // 找到尽量接近 min 的最大下标
        for ( ; i < len; i++) {
            if (clips[i][0] === min || clips[i][0] > min) {
                break;
            }
        }
        
        if (i === len || clips[i][0] > min || clips[i][1] < max) {
            min--;
            i = j;
            if (min === 0) {
                return -1;
            }
            continue;
        }
        while (i < len && clips[i][0] === min) {
            max = Math.max(max, clips[i++][1]);
        }
        min = max;
        ans++;
        if (min >= T) {
            return ans;
        }
        j = i;
        
    }

    return -1;
};

解法2：贪心

  解法 2 大致思路和解法 1 相同，反思解法1中的错误用例，解法1 中的错误之处就在过于贪心的寻找下一片段，即认为下一片段总是与上一片段的结束时刻更加临近，这样的解释可能会不知道我在说什么。。。

  举个例子：

  这是最后一个用例排序后的部分数据：

[
  [ 0, 22 ],  [ 0, 26 ],  [ 0, 28 ],  
  [ 26, 38 ], [ 26, 77 ], [ 28, 48 ], [ 30, 32 ],
  [ 72, 81 ], [ 73, 83 ], [ 74, 76 ], [ 81, 84 ], [ 81, 88 ]
]
T = 72

  按照解法1，它会先找到 0 开头的片段中的结束时刻最大值，即 [0, 28] 中的 28，然后转而寻找 28 开头的片段中的最大值，只有一个：[28, 48]，然后再继续寻找…

  但是，其实找完第一个 [0, 28] 后，再选取一个 [26, 77] 就能完成覆盖 [0, 72] 的要求了。

  因此，修改一下解法 1 中的代码：在寻找下一片段时，开始时刻在 min 之内的片段中搜索，找到结束时刻最大的那个片段，再以那个最大结束时刻作为新的 min

JS 代码如下：

var videoStitching = function(clips, T) {
    let min, max;
    let len = clips.length;
    let ans = 0;
    clips.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });

    if (clips[0][0] > 0 || clips[len-1][1] < T) {
        return -1;
    }

    min = max = 0;

    let i = 0, j = 0;
    while (i < len) {
        // 从开始时刻小于min的片段中找到最大的片段
        for (i = j; i < len; i++) {
            if (clips[i][0] > min) {
                break;
            }
            max = Math.max(max, clips[i][1]);
        }
        if (max <= min) {
            return -1;
        } else {
            j = i;
            min = max;
            ans++;
        }
        if (max >= T) {
            return ans;
        }
    }

    return -1;
};

解法3：动态规划

  这题没有往动态规划方面考虑，我还是太菜了唉，思路不难，遍历范围 0 - T，范围 i 的最少拼接数量能由范围 i-1 获得，具体细节移步官方解答

 目录