1024. Video Stitching

──────────────────────────────────────────────────────────────────────

1024. Video Stitching

給定許多片段 [start, end]，問最少要挑幾段才能把 [0, time] 完整覆蓋起來，做不到就回傳 -1。

clips = [[0, 3], [2, 4], [4, 11], [1, 2]]
time = 10
candidates = [[0, 3], [2, 4], [4, 11]]
ans = 3

思路

跟 435 和 452 那種「互斥」的區間題不同，這題允許重疊，而且重疊是好事 —— 我們要的是不留空洞，不是不重疊。這是區間題的一個大分界。

要回答的其實只有三個問題：從哪裡開始、下一段選哪個、什麼時候停。

從哪裡開始

一定要有片段從 0 或更早的位置開始，否則開頭那段就永遠補不起來，直接 -1。

下一段選哪個

假設目前已經連續覆蓋到 currEnd，那麼所有 start ≤ currEnd 的片段都是可以接上去的候選（端點相接也可以，[0,3] 接 [3,8] 中間沒有洞）。

在這些候選裡，該選哪一個？選 end 最大的那一個。

clips = [[0, 2], [0, 4], [0, 8], [0, 10], [2, 10]]
time = 10
candidates = [[0, 10]]
ans = 1

這個例子很清楚：起點都是 0 的四段裡，只有 [0, 10] 值得選，其他三段都被它完全蓋住。選了它就直接結束，選別的都得再補一段。

交換論證：假設最佳解在這一步選了 X，而我選的是 end 最大的 Y（所以 Y.end ≥ X.end）。把最佳解裡的 X 換成 Y —— 因為 Y 一樣接得上（Y.start ≤ currEnd），而且覆蓋得比 X 更遠，原本能接在 X 後面的片段一樣接得到 Y 後面。段數不變，仍然是最佳解。

所以每一步直接拿最遠的就好，不需要回頭試別的組合。更多這類判斷見 Greedy 模板。

這就是 Jump Game 的區間版

寫到這裡會發現這題跟 55. Jump Game 是同一個骨架：

	55	1024
手上維護的	能到的最遠處 farthest	已覆蓋到的最遠處 currEnd
誰能貢獻	座標 i ≤ farthest	片段 start ≤ currEnd
問的問題	到不到得了終點	最少幾段能蓋到 time

差別只在 55 只要回答「能不能」，掃一遍取 max 就結束了；而這題要數「幾段」，所以必須分層 —— 每用掉一段就是一層，同一層裡能接上的片段全部一起取 max，再一次跳到新的 currEnd。

分層這件事就是下面那兩層 while 的由來。

什麼時候停

• currEnd >= time —— 蓋到了，回傳目前用掉的段數
• 某一層裡一段都接不上（clips[i][0] > currEnd）—— 出現了補不起來的洞，回傳 -1

解題方向

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        clips.sort(key=lambda x: (x[0],-x[1]))

        res = 0
        i = 0
        n = len(clips)
        currEnd = 0
        nextEnd = 0

        while i < n and clips[i][0] <= currEnd:
            while i < n and clips[i][0] <= currEnd:
                nextEnd = max(nextEnd, clips[i][1])
                i += 1
            res+=1
            currEnd = nextEnd
            if currEnd >= time:
                return res

        return -1

兩個變數的分工是這題的關鍵：

• currEnd —— 已經確定覆蓋到哪裡，只在用掉一段之後才更新
• nextEnd —— 這一層掃過的片段中，最遠能到哪裡

內層 while 把所有 start ≤ currEnd 的片段一次吃完，只留下最大的 end；跳出內層代表這一層挑完了，res += 1 記一段，currEnd 跳到 nextEnd。

外層的條件 clips[i][0] <= currEnd 同時擔任了失敗的偵測：如果下一個片段的起點已經超過 currEnd，代表中間有洞補不起來，迴圈直接結束並回傳 -1。第一輪進不去也是同樣的道理 —— 沒有任何片段從 0 開始。

i 只會往前不會倒退，所以每個片段最多被看一次。

補充

排序的第二個 key 其實可以拿掉。 key=lambda x: (x[0], -x[1]) 裡的 -x[1] 是想讓「同起點時結束最晚的排前面」，但這件事 nextEnd = max(nextEnd, clips[i][1]) 已經做掉了 —— 內層迴圈本來就會掃過所有接得上的片段並取最大值，順序不影響結果。

留著不會錯，但要知道真正決定選誰的是那個 max，不是排序。有些寫法會反過來：只按起點排、然後靠排序保證第一個就是最好的，那種寫法才真的需要第二個 key。

端點相接算接得上。 條件是 clips[i][0] <= currEnd（含等號），因為 [0,3] 和 [3,8] 之間沒有空隙。這跟 452 的「碰到就算重疊」是同一件事的正面說法 —— 只是那題重疊代表「省一支箭」，這題重疊代表「接得起來」。

區間題的兩大類：

目標	重疊是	例題
選出互不重疊的最多／最少	壞事，要避開	435、452、253
把一段範圍蓋滿	好事，靠它補洞	1024
整理形狀（合併／插入／取交集）	不做選擇	56、57、986

前兩類是貪心，第三類只是掃描。整套見 Intervals 模板。

複雜度

• 時間 $O(n\log n)$ — 排序主導；兩層 while 加起來每個片段只被走一次，是 $O(n)$
• 空間 $O(1)$ — 只有 res、i、currEnd、nextEnd（不計 Python sort 本身最壞 $O(n)$ 的暫存）

其中 $n$ 是片段數量。注意 time 不影響複雜度 —— 我們從來沒有真的逐格走過 [0, time]，只在片段的端點上跳。