1024. Video Stitching

题目信息

题号:

1024

难度:

Medium

主题:

时间区间、片段裁剪、最少覆盖

原题:

LeetCode 1024

重点:

每个视频片段可以任意裁剪后使用;需用最少原始片段连续覆盖整个闭区间 [0, time],无法覆盖时返回 -1

题目重述

给定若干视频片段 clips,其中 clips[i] = [start_i, end_i] 表示该片段覆盖的时间区间。一个片段可以被裁剪成其内部任意连续子区间后参与拼接。

请选取最少数量的原始片段,使它们经过必要裁剪后能够无空隙地覆盖从时间 0 到 time 的全部内容。若不存在完整覆盖方案,返回 -1。

1 <= clips.length <= 100,0 <= start_i <= end_i <= 100,1 <= time <= 100。

自建示例

相邻片段必须形成连续覆盖:

输入:clips = [[0,2],[1,5],[4,7]], time = 7
输出:3
解释:三个片段依次覆盖 [0,2]、[1,5] 和 [4,7]。任意两个片段都无法从 0 连续覆盖到 7,因此至少需要三个。

片段之间存在无法填补的空隙:

输入:clips = [[0,1],[2,4]], time = 4
输出:-1
解释:时间 1 到 2 之间没有任何片段覆盖,即使裁剪片段也无法消除空隙。