Video Stitching - Practice Coding Problems

Video Stitching - Problem

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.

Input & Output

Example 1 — Basic Coverage

$ Input: clips = [[0,2],[1,9],[1,5],[3,8]], time = 5

› Output: 1

💡 Note: Clip [1,9] alone covers the entire interval [0,5], so only 1 clip is needed

Example 2 — Multiple Clips Needed

$ Input: clips = [[0,1],[1,2]], time = 5

› Output: -1

💡 Note: The clips only cover [0,2] but we need to cover [0,5], making it impossible

Example 3 — Optimal Combination

$ 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,6],[5,7],[6,9]], time = 9

› Output: 3

💡 Note: Use clips [0,4], [2,6], [6,9] to cover [0,9] with minimum 3 clips

Constraints

1 ≤ clips.length ≤ 100
0 ≤ start_i ≤ end_i ≤ 100
1 ≤ time ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Video clips with start/end times and target duration

Process

Find minimum clips to cover [0, time]

Output

Minimum number of clips needed

Key Takeaway

🎯 Key Insight: Use greedy approach - always pick the clip that extends coverage furthest from current position

Asked in

G Google 15 a Amazon 12 Apple 8 m Microsoft 6

The key insight is to use a greedy approach: always pick the clip that extends the current coverage furthest. Sort clips by start time, then iteratively select clips that maximize coverage extension. Best approach is greedy with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Minimum Clips DP	O(time × n)	O(time)	Use DP array where dp[i] = minimum clips to cover [0,i]
Brute Force - Try All Combinations	O(2ⁿ × n)	O(n)	Try every possible combination of clips to find minimum count
Greedy - Maximum Coverage Extension	O(n log n)	O(1)	Greedily select clips that extend coverage furthest at each step

Dynamic Programming - Minimum Clips DP — Algorithm Steps

Initialize dp array with infinity
For each clip, update all positions it can cover
Return dp[time] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Create dp array where dp[i] = min clips for [0,i]

Fill DP Table

For each position, try all clips that cover it

Get Result

dp[time] gives minimum clips for full coverage

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int clips[][2], int clipsSize, int time) {
    // dp[i] = minimum clips needed to cover [0, i]
    int* dp = (int*)malloc((time + 1) * sizeof(int));
    for (int i = 0; i <= time; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int i = 1; i <= time; i++) {
        for (int k = 0; k < clipsSize; k++) {
            int start = clips[k][0];
            int end = clips[k][1];
            
            // If this clip covers position i
            if (start <= i && i <= end) {
                // Check how far back this clip can help
                for (int j = max(0, start); j <= i; j++) {
                    if (dp[j] != INT_MAX) {
                        dp[i] = min(dp[i], dp[j] + 1);
                        break;
                    }
                }
            }
        }
    }
    
    int result = dp[time] == INT_MAX ? -1 : dp[time];
    free(dp);
    return result;
}

int main() {
    int clips[100][2];
    int clipsSize = 0;
    int time;
    
    // Simple parsing - read clips manually
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse clips array (simplified)
    char* ptr = line + 1; // Skip opening bracket
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            sscanf(ptr, "[%d,%d]", &clips[clipsSize][0], &clips[clipsSize][1]);
            clipsSize++;
        }
        ptr++;
    }
    
    scanf("%d", &time);
    
    int result = solution(clips, clipsSize, time);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(time × n)

For each time position, we check all n clips to see which ones cover it

✓ Linear Growth

Space Complexity

O(time)

DP array of size time to store minimum clips for each position

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Minimum Clips DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler