#1024

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Video Stitching

Solve the "Video Stitching" problem using state transition dynamic programming to cover a sporting event with minimum clips.

array dynamic programming greedy

Problem Statement

You are given a series of video clips from a sporting event that lasted time seconds. These clips may overlap and vary in length. Each clip is described as [starti, endi], where starti is the starting time and endi is the ending time of the clip. Your task is to determine the minimum number of clips required to cover the entire event, from 0 to time.

You can use the clips freely and cut them into smaller segments, but the goal is to minimize the number of clips used. If it is impossible to cover the full time duration with the given clips, return -1.

Examples

Example 1

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

Output: 3

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

We cannot 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

We can take clips [0,4], [4,7], and [6,9].

Constraints

1 <= clips.length <= 100
0 <= starti <= endi <= 100
1 <= time <= 100

Solution Approach

Sort Clips by Start Time

To approach the problem effectively, first sort the clips based on their starting times. This step allows us to evaluate each clip in sequence and decide whether it can contribute to covering the event, starting from the earliest possible time.

Apply State Transition Dynamic Programming

Use dynamic programming to keep track of the minimum clips required to cover the event up to each time point. Transition between states based on overlapping intervals to determine the optimal way to cover the entire event with the fewest clips.

Greedy Approach for Efficiency

After sorting, apply a greedy approach to select the most optimal clip for extending the coverage. This will help in minimizing the number of clips while ensuring complete coverage of the event duration.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting step, which is O(n log n), followed by a linear pass through the clips, making the overall complexity O(n log n). The space complexity is O(n) due to the dynamic programming array used to track the minimum clips required.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy

Note that if there are multiple sub-intervals with the same starting point, it is optimal to choose the one with the largest right endpoint.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#1130 minimum cost tree from leaf values #871 minimum number of refueling stops #1262 greatest sum divisible by three