【DP】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.

Python3 实现：

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])