Video stitching

Array Dynamic Programming Greedy

52.5% acceptance

Feb 25, 2026

1856

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] = [starti, endi] indicates that the ith clip started at starti and ended at endi. 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn video_stitching(clips: Vec<Vec<i32>>, time: i32) -> i32 {
    let mut dp = vec![i32::MAX; (time+1) as usize];
    dp[0] = 0;
    for t in 1..=time as usize {
      for c in &clips {
        let (s, e) = (c[0] as usize, c[1] as usize);
        if s < t && t <= e && dp[s] != i32::MAX {
          dp[t] = dp[t].min(dp[s] + 1);
        }
      }
    }
    if dp[time as usize] == i32::MAX { -1 } else { dp[time as usize] }
  }
}