视频拼接

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，1024. Video Stitching

先看题目描述

image-20201025155631527

大意就是 clips 代表一个个视频片段，给定一个 T 代表目标是覆盖区间 [0, T]，问要覆盖区间 [0, T] 至少需要 clips 中的几个片段，若无法i覆盖的话则返回 -1

算法和思路

贪心算法

注意到对于所有左端点相同的子区间，其右端点越远越有利。且最佳方案中不可能出现两个左端点相同的子区间。于是我们预处理所有的子区间，对于每一个位置 i，我们记录以其为左端点的子区间中最远的右端点，记为 maxn[i]

具体地，我们枚举每一个位置，假设当枚举到位置 i 时，记左端点不大于 i 的所有子区间的最远右端点为 last。这样 last 就代表了当前能覆盖到的最远的右端点

每次我们枚举到一个新位置，我们都用 maxn[i] 来更新 last。如果更新后 last==i，那么说明下一个位置无法被覆盖，我们无法完成目标

同时我们还需要记录上一个被使用的子区间的结束位置为 pre，每次我们越过一个被使用的子区间，就说明我们要启用一个新子区间，这个新子区间的结束位置即为当前的 last。也就是说，每次我们遇到 i==pre，则说明我们用完了一个被使用的子区间。这种情况下我们让答案加 1，并更新 pre 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int videoStitching(int[][] clips, int T) {
        int[] maxn = new int[T];
        int last = 0, res = 0, pre = 0;
        for (int[] clip : clips) {
            if (clip[0] < T) {
                maxn[clip[0]] = Math.max(maxn[clip[0]], clip[1]);
            }
        }
        for (int i = 0; i < T; i++) {
            last = Math.max(last, maxn[i]);
            if (i == last) {
                return -1;
            }
            if (i == pre) {
                res++;
                pre = last;
            }
        }
        return res;
    }
}