Leetcode 每日一题
题目链接： 1024. 视频拼接
解题思路： 将给定的区间进行预处理，获得每个左端点对应的最大的有端点。在整个区间上进行遍历，每次动态更新能达到的最大长度，对每个区间进行覆盖，若某个区间全部被覆盖，则区间数量+1。
题解：
class Solution:def videoStitching(self, clips: List[List[int]], T: int) -> int:# 以左端点开头的最大右端点max_index = [0 for i in range(T + 1)]for example in clips:# print(example)if example[0] <= T:max_index[example[0]] = max(max_index[example[0]], example[1])# cnt记录片段数量， pre记录前一个找到的右端点位置，last表示当前的最大右端点cnt, pre, last = 0, 0, 0for t in range(T):last = max(max_index[t], last)# 有空缺， 不能完全覆盖。 由于t < T所以不用担心最后一个元素if t == last:return -1# 匹配到前一个的结尾，覆盖了整个区间，可以找新的区间了 if t == pre:cnt += 1pre = lastreturn cnt