1024-视频拼接(Video Stitching)

原文链接: https://leetcode-cn.com/problems/video-stitching

英文原文

You are given a series of video clips from a sporting event that lasted time seconds. These video clips can be overlapping with each other and have varying lengths.

Each video clip is described by an array clips where clips[i] = [start_i, end_i] indicates that the ith clip started at start_i and ended at end_i.

We can cut these clips into segments freely.

For example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event [0, time]. If the task is impossible, return -1.

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: 
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We can't cover [0,5] with only [0,1] and [1,2].

Example 3:

Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].

Example 4:

Input: clips = [[0,4],[2,8]], time = 5
Output: 2
Explanation: Notice you can have extra video after the event ends.

Constraints:

1 <= clips.length <= 100
0 <= start_i <= end_i <= 100
1 <= time <= 100

中文题目

你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

使用数组 clips 描述所有的视频片段，其中 clips[i] = [start_i, end_i] 表示：某个视频片段开始于 start_i 并于 end_i 结束。

甚至可以对这些片段自由地再剪辑：

例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

示例 1：

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出：3
解释：
选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。

示例 2：

输入：clips = [[0,1],[1,2]], time = 5
输出：-1
解释：
无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 3：

输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
输出：3
解释： 
选取片段 [0,4], [4,7] 和 [6,9] 。

示例 4：

输入：clips = [[0,4],[2,8]], time = 5
输出：2
解释：
注意，你可能录制超过比赛结束时间的视频。

提示：

1 <= clips.length <= 100
0 <= start_i <= end_i <= 100
1 <= time <= 100

通过代码

高赞题解

这里给出两种常见解法

对于这道题, 一个非常常见的解法是排序后贪心, 大家可以参考这题POJ-2376, 做法基本就是一样的. 它的思路很简单: 按照先左端点后右端点的排序规则之后, 尽量的向后贪心(当然与前面的有交叉). 时间复杂度是: 排序O(N * logN) + 贪心O(N).

class Solution {
public:
    static const int N = 1e2 + 5;
    int len;
    // 贪心
    struct Node {
        int start, end;
        bool operator<(const Node &rhs) const {
            if (start == rhs.start) return end < rhs.end;
            return start < rhs.start;
        }
    }A[N];

    int videoStitching(vector<vector<int>>& clips, int T) {
        for (int i = 0; i < clips.size(); ++i) {
            A[i + 1].start = clips[i][0];
            A[i + 1].end = clips[i][1];
        }
        len = clips.size();
        std::sort(A + 1, A + 1 + len);
        int R = 0, tmp_R = 0, cnt = 0;
        for (int i = 1; i <= len; ++i) {
            if (A[i].start <= R) {
                tmp_R = std::max(tmp_R, A[i].end);
            } else {
                if (A[i].start > tmp_R) break;
                ++cnt;
                R = tmp_R;
                --i;
            }
            if (R >= T) break;
        }
        // 考虑结尾处
        if (tmp_R > R) ++cnt, R = tmp_R;
        if (R >= T) return cnt;
        else return -1;
    }
};

第二种少见的做法是dp(因为复杂度较高大家都写第一种, 所以少见), 但是在数据范围可以过的前提下, dp写起来更简单, 代码也更短. 看到时间序列, 很容易想到, 定义dp[i]为覆盖前i个时间段, 所需要的最少的数目. 转移也很常见, 枚举每个可能的片段. 时间复杂度O(N ^ 2)

class Solution {
public:
    static const int N = 1e2 + 5;
    // dp[i]表示覆盖[0, i]这个片段过称, 最少需要的数目
    int dp[N];

    int videoStitching(vector<vector<int>>& clips, int T) {
        std::memset(dp, 0x3f3f3f3f, sizeof dp);
        // 递推的起点
        dp[0] = 0;
        for (int i = 1; i <= T; ++i) {
            // 转移, 枚举每一种可能的情况
            for (int k = 0; k < clips.size(); ++k) {
                if (clips[k][0] <= i && clips[k][1] >= i)
                    dp[i] = std::min(dp[i], dp[clips[k][0]] + 1);
            }
        }
        if (dp[T] >= 1e9) return -1;
        else return dp[T];
    }
};

多说一点, 这类dp非常常见, 类似的如以前i个物品的最大值, 前i个元素且以第i个元素结尾的最大值, 等等…, 其实都是一样的, 通过多刷题, 多思考, 多总结, 这类dp的解法都是非常显然的.
还有为什么有人觉得很多题(不单指这道题)非常简单, 是他们口中的傻逼题, 套路题. 因为对于绝大部分的编程高手来说, 他们都见过/写过类似的题目上十上百遍了.
还有为什么大家常说量变引起质变, 因为对于绝大部分非天才选手来说, 如果不能做到举一反三, 那么做到举三反一, 举十反一, 也是可以成长为非常非常牛逼的编程高手.
最后说一点题外话, 绝大部分的编程高手都不会怎么详细写题解, 因为写出一篇详细的题解所需要耗的时间通常是解出一道题的4, 5倍或许还要多的时间, 所以绝大部分他们都不愿意花费这些时间(~~有这时间还不如多刷几道题呢~~), 所以如果大家看到好的题解尽量点赞捧场, 算是给予写详细题解人的激励吧, 或许这样更多的编程高手愿意分享他们的解法, 思路, 心得等. (ps本人并不是什么编程高手, 纯属有感而发)
~~最后, 不要脸的打个自己github上的广告, 欢迎star, 感谢捧场lol~~.
Algorithm-challenger
经典的几道贪心题
 dp专题系统学习, 难度基本从易到难再到易, 里面dp题的难度可能并非严格从易到难的, 后续可能会按难度重新排序一下, 或者按照各类dp, 如区间dp, 数位dp这些分一下类, 但是看的人以及反馈的人实属太少了, 没有什么更新的动力, 所以一直被搁浅了. 但我一直是想做好这件事的哈哈哈lol

统计信息

通过次数	提交次数	AC比率
34466	62001	55.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途