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)
