---
title: "1024. Video Stitching"
url: "https://laigary.com/interview/coding/1024-video-stitching"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Greedy", "Intervals", "Classic"]
---

# 1024. Video Stitching

[1024\. Video Stitching](https://leetcode.com/problems/video-stitching/)

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

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

## 思路

跟 [435](/interview/coding/435-non-overlapping-intervals) 和 [452](/interview/coding/452-minimum-number-of-arrows-to-burst-balloons) 那種「互斥」的區間題不同，**這題允許重疊，而且重疊是好事** —— 我們要的是不留空洞，不是不重疊。這是區間題的一個大分界。

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

### 從哪裡開始

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

### 下一段選哪個

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

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

```python
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 模板](/interview/coding/greedy-template)。

### 這就是 Jump Game 的區間版

寫到這裡會發現這題跟 [55. Jump Game](/interview/coding/55-jump-game) 是同一個骨架：

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

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

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

### 什麼時候停

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

## 解題方向

```python
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](/interview/coding/452-minimum-number-of-arrows-to-burst-balloons) 的「碰到就算重疊」是同一件事的正面說法 —— 只是那題重疊代表「省一支箭」，這題重疊代表「接得起來」。

**區間題的兩大類**：

| 目標 | 重疊是 | 例題 |
|---|---|---|
| 選出互不重疊的最多／最少 | 壞事，要避開 | [435](/interview/coding/435-non-overlapping-intervals)、[452](/interview/coding/452-minimum-number-of-arrows-to-burst-balloons)、[253](/interview/coding/253-meeting-rooms-ii) |
| 把一段範圍蓋滿 | 好事，靠它補洞 | 1024 |
| 整理形狀（合併／插入／取交集） | 不做選擇 | [56](/interview/coding/56-merge-intervals)、[57](/interview/coding/57-insert-interval)、[986](/interview/coding/986-interval-list-intersections) |

前兩類是貪心，第三類只是掃描。整套見 [Intervals 模板](/interview/coding/intervals-template)。

## 複雜度

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

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