What is the primary pattern to solve the "Video Stitching" problem?

The primary pattern is state transition dynamic programming, which is used to find the optimal number of clips needed to cover the event.

How can sorting the clips help in solving the problem?

Sorting the clips by their start time ensures that we can process them in a sequence, simplifying the process of choosing which clip to use next in a greedy fashion.

What happens if no valid combination of clips is found?

If no valid combination of clips covers the entire event, the answer will be -1, indicating that it's impossible to fully cover the event with the given clips.

What if the clips have overlapping segments? How does this affect the solution?

Overlapping clips can be utilized in dynamic programming, allowing us to transition between states and cover the event optimally. The greedy approach helps minimize the number of clips used.

How does GhostInterview help in solving the "Video Stitching" problem?

GhostInterview helps you practice the problem by offering step-by-step guidance through dynamic programming and greedy strategies while highlighting common mistakes to avoid.

#1024

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

视频拼接

你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。使用数组 clips 描述所有的视频片段，其中 clips[i] = [start i , end i ] 表示：某个视频片段开始于 start i 并于 end i 结束。甚至…

数组动态规划贪心

题目描述

你将会获得一系列视频片段，这些片段来自于一项持续时长为 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] 。

提示：

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

lightbulb

解题思路

方法一：贪心

注意到，如果相同起点的子区间有多个，那么选择右端点最大的那个子区间是最优的。

因此，我们可以预处理所有子区间，对于每一个位置 $i$ ，算出所有以 $i$ 为起点的子区间中，右端点最大的那个位置，记录在数组 $last[i]$ 中。

我们定义变量 mx 表示当前能够到达的最远位置，变量 ans 表示当前需要的最少子区间数，变量 pre 表示上一个被使用的子区间的右端点。

接下来，我们从 $0$ 开始枚举所有位置 $i$ ，用 $last[i]$ 来更新 mx。如果更新后 $mx = i$ ，说明无法覆盖下一个位置，因此无法完成任务，返回 $-1$ 。

同时我们记录上一个被使用的子区间的右端点 pre，如果 $pre = i$ ，说明需要使用一个新的子区间，因此我们将 ans 加 $1$ ，并将 pre 更新为 mx。

遍历结束后，返回 ans 即可。

时间复杂度 $O(n+m)$ ，空间复杂度 $O(m)$ 。其中 $n$ 和 $m$ 分别是数组 clips 的长度和 time 的值。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate applies sorting as the first step.
question_mark
Look for a clear explanation of state transitions in dynamic programming.
question_mark
Evaluate if the candidate applies a greedy approach to optimize the solution.

warning

常见陷阱

外企场景

error
Failing to sort the clips before applying dynamic programming leads to incorrect results.
error
Overcomplicating the state transitions without considering the greedy choice may make the solution inefficient.
error
Not handling edge cases, such as when it's impossible to cover the event with the given clips, results in returning an incorrect value.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where clips can overlap multiple times and how the solution adapts.
arrow_right_alt
What if the clips are not sorted beforehand? Can the problem still be solved efficiently?
arrow_right_alt
How would the problem scale with larger inputs? Consider optimization techniques.

help

常见问题

外企场景

继续练习

#1130 叶值的最小代价生成树 #871 最低加油次数 #1262 可被三整除的最大和