1024. Video Stitching
1024. Video Stitching
问题描述：
You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation:
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].Example 2:
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation:
We can't cover [0,5] with only [0,1] and [0,2].Example 3:
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation:
We can take clips [0,4], [4,7], and [6,9].Example 4:
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation:
Notice you can have extra video after the event ends.Note:
1 <= clips.length <= 100
0 <= clips[i][0], clips[i][1] <= 100
0 <= T <= 100解题思路：
这道题刚开始理解错了题目，导致在写代码的时候陷入一个大坑。注意，clips 里面的片段是从一个完整运动视频中分割出来的，因此所有片段连起来肯定是连续的，不会出现 [0,2] [5,7]，而中间少了一段这种情况。
思路是：找到一个视频之后，下一个视频应该跟上一个视频可以连上，同时保证延续的时间最长。因此，要对 clips 按照开始时间从小到大排序，如果开始时间相同，按照结束时间从小到大排序。实际上，在 Python 中，clips.sort() 就可以完成这样的操作。
观察到，将 clips 排序后，第一个视频应从 0 开始，最后一个视频的结束时间应该大于T，否则返回-1。
举个例子，如 clips = [[0,1],[0,2],[0,3],[1,2],[1,3],[1,4]]，T =4。从左到右遍历，用一个 index 记录遍历的位置，start = 0 和 end = 0 记录已选择视频的开始时间和结束时间，minl = 0 记录片段数。
- 先有外层循环
while end < T:表示还没有到达 T。 - 内层 while 循环中，如果当前 clip 的开始时间小于 start，则更新 index 和 end，这样就可以到达 clip = [0, 3] 的位置，此时 start = 0，end = 3，index = 3。遍历到 clip = [1, 2]，不满足 while 循环条件，则跳出循环，将 start 更新为 end，minl 加 1，并且 index 不要移动 （因为 end 已经到 3 的位置了，start 变为 end 值，可以让当前片段在内层循环继续判断）。此时，clips = [1, 2] 再次经过内层 while 循环时，由于 start = 3，因此可以继续向右滑动。最后，到达 clip = [1, 4] 的位置，end = 4，不满足外层 while 循环条件，退出。注意，如果滑动到 clips 的末尾还没有到达 T，则返回 -1.
Python实现：
class Solution:
def videoStitching(self, clips, T):
clips.sort() # 先按照一维升序，再按照二维升序
if clips[0][0] > 0 or clips[-1][1] < T:
return -1
minl = 0
start = end = 0
index = 0 # 记录当前片段的位置
while end < T:
# 对于 [0,1] [0,2] [0,3] 这种，往右滑动
while index < len(clips) and clips[index][0] <= start:
end = max(end, clips[index][1])
index += 1
# 对于 [1,2] [1,4] 这种，更新 start 为 end，更新片段数长度
# 但不滑动，下一次当前片段会重新进入上一个 while 判断是否滑动
if index - 1 < len(clips):
start = end
minl += 1
else: # 滑动到末尾也滑不到 T 的位置
return -1
return minl
clips = [[0,1],[0,2],[0,3],[1,2],[1,3],[1,4]]
print(Solution().videoStitching(clips, 4)) # 2 ([0,3][1,4])
clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]]
print(Solution().videoStitching(clips, 9)) # 3 ([0,4][4,7][6,9])