[算法] 力扣 1024. 视频拼接

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.length <= 100
0 <= clips[i][0] <= clips[i][1] <= 100
0 <= T <= 100

class Solution {
    public int videoStitching(int[][] clips, int T) {
        // step 1
        var ints = new int[T + 1];
        for (var clip : clips)
            if (clip[0] < ints.length && ints[clip[0]] < clip[1])
                ints[clip[0]] = clip[1];
        // step 2
        var left = 0;
        var right = 0;
        var max = 0;
        var count = 0;
        while (max < T) {
            for (var i = left; i <= right; i++)
                if (ints[i] > max)
                    max = ints[i];
            if (max <= right)
                return -1;
            count++;
            left = right + 1;
            right = max;
        }
        return count;
    }
}

示例 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]。

Step 1

先开一个int[]数组ints，ints[i]的值表示所有从i开始的片段，最大结束时间。

（举例：[1,9],[1,5]两个片段显然是用前者进行剪切更好）

这一步完成后的ints的内容如图所示：

Step 2

划定初始区间[left, right]和初始最大结束时间，在ints的这个区间中找到大于最大结束时间的值。找不到直接返回-1，否则修改区间，继续寻找直到最大结束时间不小于值T。

第1次：[0, 0], 0, 区间内最大值为2

第2次：[1, 2], 2, 区间内最大值为9

第3次：[3, 9], 9, 区间内最大值为10，结束寻找（如果此时ints[8]的值为9，会导致函数直接返回-1）