1024. Video Stitching¶
题目信息¶
- 题号:
1024
- 难度:
Medium
- 主题:
时间区间、片段裁剪、最少覆盖
- 原题:
- 重点:
每个视频片段可以任意裁剪后使用;需用最少原始片段连续覆盖整个闭区间
[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 之间没有任何片段覆盖,即使裁剪片段也无法消除空隙。