We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Video Stitching

Number: 1081

Difficulty: Medium

Paid? No

Companies: Google, Amazon, TikTok

Problem Description

Given an array of video clips where each clip is represented as [start, end], determine the minimum number of clips required to cover the entire event time interval [0, time]. Clips may overlap and can be cut into smaller segments if needed. If it is not possible to cover the interval, return -1.

Key Insights

  • The problem can be approached using a greedy algorithm due to the ability to select the clip that extends coverage the furthest at each step.
  • Sort the clips based on start time to efficiently determine the next potential clip.
  • While iterating, maintain two pointers: one for the current coverage end and another for the farthest reachable end from the clips whose start time is within the current coverage.
  • If at any stage no clip can extend the current coverage, the task is impossible.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting; the subsequent traversal is O(n).
Space Complexity: O(1) (ignoring the space used for input storage).

Solution

We use a greedy algorithm combined with sorting:

  1. Sort all clips by their starting times.
  2. Initialize currentEnd to 0 (indicating the current coverage) and count to track the number of clips chosen.
  3. Iterate through the clips while currentEnd < time. For each iteration, determine the farthest end (nextEnd) reachable from any clip whose start is within currentEnd.
  4. If nextEnd remains unchanged, it means no clip can extend the coverage, so return -1.
  5. Otherwise, update currentEnd to nextEnd and increment the count.
  6. End the loop when currentEnd reaches or exceeds the event's time.

This greedy selection ensures minimum clips are used by always choosing the clip that provides the best extension.

Code Solutions

# Python solution for Video Stitching
def videoStitching(clips, time):
    # Sort clips by their starting time
    clips.sort(key=lambda x: x[0])
    
    # Initialize variables:
    # current_end stores the current reach of the stitched clips.
    # next_end stores the farthest reach while exploring clips within current range.
    # count tracks number of clips selected.
    current_end = 0
    next_end = 0
    count = 0
    i = 0
    n = len(clips)
    
    # Continue until the entire event is covered
    while current_end < time:
        # Check extension from all clips whose start is within current_end
        while i < n and clips[i][0] <= current_end:
            next_end = max(next_end, clips[i][1])
            i += 1
        
        # If no clip can extend the current coverage, return -1 (coverage gap)
        if current_end == next_end:
            return -1
        
        # Update current_end to next_end (extend coverage)
        current_end = next_end
        count += 1  # Increment the count as we've chosen another clip
    
    return count

# Example usage:
print(videoStitching([[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], 10))
← Back to All Questions