Domain 2MediumMEDIUM

Video Stitching

LeetCode problem 1024: Video Stitching (medium).

Domain: medium•Updated: 2026-09-06
#Dynamic Programming

Problem Breakdown

We are tasked with covering a continuous time interval [0, T]. We have a collection of video clips defined as intervals [start, end]. The key constraint here is that we can cut these clips freely; this means if we need coverage from 2 to 5, and we have a clip [1, 6], we effectively utilize the segment [2, 5] within it.

Inputs:

  • clips: A list of intervals (start time, end time).
  • T: The target duration ending at second T. We need to cover up to and including this point.

Outputs:

  • An integer representing the minimum number of clips required to stitch together a continuous coverage from 0 to T.
  • -1 if it is impossible to achieve full coverage (e.g., gaps exist, or we cannot reach T).

Implicit Constraints & Edge Cases:

  • Gaps: If there are no clips starting at time 0, or if the maximum reachable end point from our current position doesn’t extend past a gap in available clips, it’s impossible.
  • Overlapping/Extra Coverage: A clip can cover [start, T] even if its original end > T. We only care about reaching exactly T, so exceeding is fine (as seen in Example 4).
  • Zero Duration: If T = 0, we technically need 0 clips. The logic should handle this naturally without crashing.

Intuition

This problem maps closely to the “Jump Game II” pattern, but with intervals instead of jump lengths.

  1. Brute Force Approach: We could try every combination of subsets of clips and check if they cover [0, T]. With NN clips, this is exponential (O(2N)O(2^N)), which will time out for even moderate inputs in an interview setting.
  2. Key Insight: Since we want the minimum number of clips to reach T, at any point where our current coverage ends (let’s call it current_end), we should greedily pick a clip that starts before or exactly when current_end and extends as far right as possible (max_reach).
  3. Why Greedy Works: If multiple clips can extend from the current position, picking the one with the furthest reach is always optimal because it gives us more “room” to pick subsequent clips later without skipping any necessary coverage time.

Approach

  1. Sort Clips: Sort clips by their start times (and end times as a tie-breaker). This allows us to process them in chronological order of availability.
  2. Initialize State:
    • current_end: The rightmost point we have currently covered continuously starting from 0. Initially 0.
    • max_reach: The furthest point reachable using clips that start within [start_of_current_segment, current_end].
    • count: Number of clips selected so far.
  3. Iterate: While we haven’t covered up to T (current_end < T):
    • Scan through available unprocessed clips (starting ≤\le current_end). Update max_reach with the maximum end time found among these valid clips.
    • If no clip extends beyond our current position (max_reach == current_end) and we still need to cover more distance, return -1.
    • Once we’ve considered all reachable clips for this segment, increment count, update current_end to max_reach.
  4. Termination: If the loop finishes with current_end >= T, return count.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N) due to sorting the clips list. The subsequent iteration is linear, O(N)O(N). Total: O(Nlog⁡N)O(N \log N).
    • Given constraints (N≤100N \le 100), this is extremely fast, but efficient logic scales better for larger inputs typical in production systems.
  • Space Complexity: O(1)O(1) auxiliary space (ignoring the sort stack). We only use a few integer variables to track state.

Solution

def videoStitching(clips: list[list[int]], T: int) -> int:
    # Sort clips by start time, then end time for consistency in greedy selection
    clips.sort() 
    
    current_end = 0      # The rightmost point we have covered continuously so far
    max_reach = 0        # Furthest point reachable using available clips starting <= current_end
    count = 0            # Number of clips selected
    
    n = len(clips)
    
    while current_end < T:
        # If there are no more clips to check or the next clip starts after our coverage ends,
        # we cannot extend further. However, we must first ensure we process all valid 
        # candidates for this step before deciding if it's impossible.
        
        # Check if any unprocessed clip can start within our current covered range
        while n > 0 and clips[0][0] <= current_end:
            max_reach = max(max_reach, clips.pop(0)[1]) 
            # Note: Popping from list is O(N), better to use index. Re-writing for optimal logic below.

    # Optimized Implementation using Indexing instead of popping
    
    i = 0
    current_end = 0
    count = 0
    
    while current_end < T and i < n:
        if clips[i][0] > current_end:
            return -1
        
        max_reach = max(max_reach, clips[i][1])
        
        # If we have processed all reachable clips for this segment but haven't extended range enough
        if not (clips[i+1][0] <= current_end) or i == n-1: 
            pass
            
    # Let's rewrite the loop cleanly to avoid index confusion
    

Wait, let me write a cleaner implementation inside the final block. The logic needs to be precise regarding indices. I will use an iterator approach for clarity in code but ensure it matches the greedy logic derived above.

Corrected Logic Flow:

  1. Sort clips.
  2. Loop while current_end < T:
    • If we are at a state where no clip starts ≤\le current_end (and there is still distance to cover), return -1.
    • Iterate through clips starting from current index until start time > current_end. Update max_reach.
    • Increment count. Set current_end = max_reach.
def videoStitching(clips: list[list[int]], T: int) -> int:
    # Sort by start time to process clips in chronological order of availability
    clips.sort() 
    
    current_end = 0      # The rightmost point we have covered continuously so far (initially 0)
    max_reach = 0        # Furthest point reachable using available clips starting <= current_end
    count = 0            # Number of clips selected
    
    n = len(clips)
    
    while current_end < T:
        if not i < n and clips[i][0] > current_end: 
             return -1
            
        max_reach = 0
        
        # Iterate through all clips that start within our currently covered range [start, current_end]
        while i < n and clips[i][0] <= current_end:
            max_reach = max(max_reach, clips[i][1])
            i += 1
            
        # If we cannot extend beyond the current end point with any available clip
        if max_reach == current_end: 
             return -1
        
        count += 1
        current_end = max_reach
    
    return count

Wait, I need to make sure i is preserved across iterations. The variable scope in Python allows this inside the function but needs initialization outside loop. Let’s ensure code block is clean and runnable.

Edge Cases Handled

  • Impossible Coverage: If a gap exists (e.g., covered up to 5, next clip starts at 7), max_reach will not increase beyond current_end, triggering the -1 return condition inside the loop.
  • T=0: The while loop condition while current_end < T is false immediately if T=0, returning count = 0.
  • Extra Coverage: If a clip ends at end > T, we update current_end to that value, but the outer loop terminates as soon as current_end >= T. This correctly handles Example 4.
  • No Clip Starts at 0: The first iteration checks if any clip starts ≤\le 0 (which is effectively start=0). If all clips start > 0 and we need to cover from 0, the inner while loop won’t run or max_reach stays 0. Since current_end=0 initially, this returns -1 immediately in next check logic if not handled carefully. My code handles: if max_reach == current_end. If no clips start ≤\le 0 (except maybe negative starts which aren’t allowed), loop doesn’t run? Wait.
    • Initialization: i=0, current_end=0.
    • Inner while checks clips[i][0] <= 0. Since constraints say start≥0start \ge 0, this only matches if start is exactly 0. If no clip starts at 0, inner loop doesn’t run? No, wait.
    • Actually, we need to handle the case where there are NO clips starting ≤\le current_end properly.
    • My logic: while i < n and clips[i][0] <= current_end. If no clip satisfies this (e.g., all start > 0), loop doesn’t run. max_reach remains initialized value? No, I need to initialize max_reach = max(current_end + something) or handle the “no valid clip” case explicitly before updating count.
    • Correction: If inner while runs but finds no clips extending range (e.g., all start ≤\le current end but also end at same point), we detect failure via if max_reach == current_end. But if NO clips satisfy condition, loop doesn’t run, max_reach stays 0? No.
    • Better: Initialize max_reach = current_end. If inner while finds better reach, update it. After inner while, check if max_reach <= current_end: return -1 (unless we already reached T).

Let’s refine the code block for maximum correctness before finalizing output.

def videoStitching(clips: list[list[int]], T: int) -> int:
    clips.sort() 
    n = len(clips)
    
    current_end = 0
    max_reach = 0
    count = 0
    
    i = 0
    
    while current_end < T and i < n:
        # If the next available clip starts after our current coverage, we have a gap.
        if clips[i][0] > current_end:
            return -1
            
        max_reach = max(max_reach, clips[i][1])
        
        # We need to find all reachable clips for this step before committing to the next jump
        while i < n and clips[i][0] <= current_end:
             max_reach = max(max_reach, clips[i][1])
             i += 1
            
        if max_reach == current_end: # Cannot extend further
            return -1
        
        count += 1
        current_end = max_reach
    
    return count

Wait, the logic while current_end < T and i < n combined with inner loop is slightly redundant. Let’s simplify to standard pattern for this problem (Jump Game II style).

Standard Pattern: Iterate while current_end < T. Inside: Find max reach of all clips starting ≤\le current_end. Increment count, update end. If no progress made (max_reach == current_end), return -1. Need to handle case where we run out of clips but haven’t reached T yet (handled by loop condition).

One specific edge case: What if the very first clip starts at 0? current_end=0. Inner while runs, updates max reach. If no clip starts ≤\le current end later on… Actually, simpler logic is often used in solutions for this problem because constraints are small (T≤100T \le 100). But sorting solution is cleaner generally. I will stick to the sorted greedy approach but ensure max_reach initialization handles “no clips found” correctly (though if no clips start ≤current_end\le current\_end, we return -1 immediately or loop finishes? If loop condition fails, it means T reached).

Let’s write the final code carefully in Python.

Problem Breakdown

We need to cover a continuous time interval [0, T] using the minimum number of clips from a given list clips. Each clip is an interval [start, end]. We can cut these intervals freely (e.g., use part of a longer clip). If we cannot form a contiguous coverage starting at 0 and ending at or before T without gaps, return -1.

Inputs:

  • clips: List of [start, end] pairs.
  • T: The target duration to cover (must reach exactly this point in time).

Outputs:

  • Integer: Minimum clips needed.
  • -1: If coverage is impossible.

Key Constraints & Edge Cases:

  • Gaps: A gap occurs if we have covered up to X, but the next available clip starts at Y > X. We must detect this and return -1.
  • Zero Duration (T=0): If T is 0, coverage [0, 0] requires 0 clips. The logic should handle this naturally (loop condition fails immediately).
  • Extra Coverage: Clips can extend beyond T; we only care about reaching T.

Intuition

This problem shares the same core structure as “Jump Game II”. We want to reach a target (T) with minimum steps. Since clips are intervals, instead of jumping fixed distances, we jump from our current coverage boundary to the furthest possible point reachable by available resources.

  1. Greedy Strategy: At any moment where we have covered [0, current_end], we look at all clips that start within this range (clip.start <= current_end). Among these valid candidates, we pick the one (or combination) that allows us to reach the furthest point max_reach.
  2. Why Greedy Works: Extending our coverage as far right as possible with each clip selection leaves maximum flexibility for subsequent clips. If a suboptimal choice was made earlier (picking a shorter range), it would only restrict future options compared to picking the longest available reach now.

Approach

  1. Sort Clips: Sort clips by start time. This allows us to process them in order of availability relative to our current coverage boundary.
  2. Iterate with State Tracking: Maintain a pointer or index for clips and track:
    • current_end: The rightmost point we have successfully covered continuously so far (initially 0).
    • max_reach: The furthest point reachable using any clip that starts ≤\le current_end.
  3. Loop Logic: While our coverage hasn’t reached T (current_end < T):
    • Check if there are clips starting within the current range. If we run out of valid clips (next available start > current_end) and haven’t extended reach, it’s a gap -> return -1.
    • Update max_reach by scanning all applicable clips for this step.
    • Increment clip count (count += 1).
    • Move our boundary to the new furthest point found (current_end = max_reach).
  4. Termination: If loop finishes and we reached or exceeded T, return count.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N), where NN is the number of clips. This is dominated by sorting. The subsequent linear scan through the sorted list takes O(N)O(N).
    • Given constraints (N≤100N \le 100, coordinates ≤100\le 100), this is highly efficient and well within limits for larger inputs as well.
  • Space Complexity: O(1)O(1) auxiliary space (excluding sort stack). We use a constant number of variables regardless of input size.

Solution

def videoStitching(clips: list[list[int]], T: int) -> int:
    # Sort clips by start time to process them in chronological order of availability
    clips.sort() 
    
    n = len(clips)
    
    current_end = 0      # The rightmost point we have covered continuously so far (initially 0)
    max_reach = 0        # Furthest point reachable using available clips starting <= current_end
    count = 0            # Number of clips selected
    
    i = 0                # Index to iterate through sorted clips
    
    while current_end < T and i < n:
        # If the next clip starts after our current coverage ends, we have a gap.
        if clips[i][0] > current_end:
            return -1
        
        max_reach = max(max_reach, clips[i][1])
        
        # Iterate through all valid clips that start within or at current_end boundary
        while i < n and clips[i][0] <= current_end:
             max_reach = max(max_reach, clips[i][1])
             i += 1
            
        # If we cannot extend beyond the current end point with any available clip
        if max_reach == current_end: 
            return -1
        
        count += 1
        current_end = max_reach
    
    return count