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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Video Stitching

Difficulty: Medium

Problem Description

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. 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.

Key Insights

  • You need to cover the interval [0, time] using the minimum number of clips.
  • Each clip can potentially cover a portion of the required interval, and they may overlap.
  • A greedy approach can be effective: always extend the coverage as far as possible with the fewest clips.
  • Sorting the clips based on their starting times helps in efficiently finding the best clip to use at each step.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of clips (due to sorting).
Space Complexity: O(1), since we can do the operations in place.

Solution

The solution uses a greedy approach where we sort the clips based on their starting times. We then iterate through them, always trying to extend our coverage as far as possible. If we reach a point where we cannot extend the coverage, we return -1. Otherwise, we count the number of clips needed to cover the entire interval.

Code Solutions

def videoStitching(clips, time):
    clips.sort()  # Sort clips by starting time
    count = 0  # Count of clips used
    end = 0  # The current end of the covered interval
    farthest = 0  # The farthest end we can reach with the current set of clips
    i = 0  # Index for clips

    while end < time:
        while i < len(clips) and clips[i][0] <= end:
            farthest = max(farthest, clips[i][1])  # Extend the farthest we can reach
            i += 1
        if end == farthest:  # No progress made
            return -1
        end = farthest  # Move to the new end
        count += 1  # Increment the count of clips used

    return count
← Back to All Questions