[算法] 力扣 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)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注