视频拼接 图解题解

这道题到底在问什么

输入

clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time=10

输出

3

最优解：一步一步想明白

1. 3记住这句：last 记每个起点的最远延伸，贪心扫描时走到当前段右端就接一段、跳到段内最远 mx。后面每帧都在套它。
2. 4先开一个长度 10 的数组 last，last[i] 记「从位置 i 起跳一步最远能到哪」，一开始都填 0。
3. 5看片段 [0,2]：从位置 0 起跳能延伸到 2，比原来的 0 远，last[0] 更新成 2。
4. 6看片段 [4,6]：从位置 4 起跳能延伸到 6，比原来的 0 远，last[4] 更新成 6。
5. 7看片段 [8,10]：从位置 8 起跳能延伸到 10，比原来的 0 远，last[8] 更新成 10。
6. 8看片段 [1,9]：从位置 1 起跳能延伸到 9，比原来的 0 远，last[1] 更新成 9。
7. 9看片段 [1,5]：位置 1 已经能到 9，比 5 更远或相等，last[1] 保持不变。
8. 10看片段 [5,9]：从位置 5 起跳能延伸到 9，比原来的 0 远，last[5] 更新成 9。
9. 11last 数组建好了。接下来从左往右扫，用 pre 记当前段右端（起步 0），mx 记这一段内能延伸到的最远。绿色格子代表已经覆盖到的位置。
10. 12位置 0 能从某个起点延伸到 2，把这一段内的最远 mx 抬到 2。
11. 13恰好走到当前段的右端 pre = 0，必须接一段新片段：ans 加到 1，把覆盖边界一口气推到这一段攒出的最远 2。
12. 14位置 1 能从某个起点延伸到 9，把这一段内的最远 mx 抬到 9。
13. 15位置 2 的起跳 last[2] = 0 到不了更远，mx 还是 9，继续往右走。
14. 16恰好走到当前段的右端 pre = 2，必须接一段新片段：ans 加到 2，把覆盖边界一口气推到这一段攒出的最远 9。
15. 17位置 3 的起跳 last[3] = 0 到不了更远，mx 还是 9，继续往右走。
16. 18位置 4 的起跳 last[4] = 6 到不了更远，mx 还是 9，继续往右走。
17. 19位置 5 的起跳 last[5] = 9 到不了更远，mx 还是 9，继续往右走。
18. 20位置 6 的起跳 last[6] = 0 到不了更远，mx 还是 9，继续往右走。
19. 21位置 7 的起跳 last[7] = 0 到不了更远，mx 还是 9，继续往右走。
20. 22位置 8 能从某个起点延伸到 10，把这一段内的最远 mx 抬到 10。
21. 23位置 9 的起跳 last[9] = 0 到不了更远，mx 还是 10，继续往右走。
22. 24恰好走到当前段的右端 pre = 9，必须接一段新片段：ans 加到 3，把覆盖边界一口气推到这一段攒出的最远 10。
23. 25扫完，覆盖边界 pre 已经到 10，盖住了整段 [0, 10]。一路接了 3 段，所以答案就是 3。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        last = [0] * time
        for a, b in clips:
            if a < time:
                last[a] = max(last[a], b)
        ans = mx = pre = 0
        for i, v in enumerate(last):
            mx = max(mx, v)
            if mx <= i:
                return -1
            if pre == i:
                ans += 1
                pre = mx
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> last(time);
        for (auto& v : clips) {
            int a = v[0], b = v[1];
            if (a < time) {
                last[a] = max(last[a], b);
            }
        }
        int mx = 0, ans = 0;
        int pre = 0;
        for (int i = 0; i < time; ++i) {
            mx = max(mx, last[i]);
            if (mx <= i) {
                return -1;
            }
            if (pre == i) {
                ++ans;
                pre = mx;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int videoStitching(int[][] clips, int time) {
        int[] last = new int[time];
        for (int[] e : clips) {
            int a = e[0], b = e[1];
            if (a < time) {
                last[a] = Math.max(last[a], b);
            }
        }
        int ans = 0, mx = 0, pre = 0;
        for (int i = 0; i < time; ++i) {
            mx = Math.max(mx, last[i]);
            if (mx <= i) {
                return -1;
            }
            if (pre == i) {
                ++ans;
                pre = mx;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问