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, 0
for t in range(T):
last = max(max_index[t], last)
# 有空缺， 不能完全覆寫， 由于t < T所以不用擔心最后一個元素
if t == last:
return -1
# 匹配到前一個的結尾，覆寫了整個區間，可以找新的區間了
if t == pre:
cnt += 1
pre = last
return cnt
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/193055.html
標籤：其他