Video Stitching

Medium

Verily

0 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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.

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We cannot cover [0,5] with only [0,1] and [1,2].

Example 3:

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,5],[5,7],[6,9]], time = 9
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].

Constraints:

1 <= clips.length <= 100
0 <= start_i <= end_i <= 100
1 <= time <= 100

Video Stitching

Medium

Verily

0 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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.

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We cannot cover [0,5] with only [0,1] and [1,2].

Example 3:

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,5],[5,7],[6,9]], time = 9
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].

Constraints:

1 <= clips.length <= 100
0 <= start_i <= end_i <= 100
1 <= time <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the clips array and the maximum value for time T?
If it's impossible to cover the entire range [0, T], what should the function return? Should I return -1, null, or throw an exception?
Can the clips in the input array overlap, and if so, how should I handle overlapping clips?
Are the start and end times of the clips guaranteed to be non-negative integers?
If there are multiple ways to cover the range [0, T] with the minimum number of clips, is any valid solution acceptable?

Brute Force Solution

Approach

The brute force method for video stitching involves checking every possible combination of video clips to see if they can cover the entire target video length. It's like trying every possible way to piece together the clips and then seeing which one uses the least amount of clips. This approach guarantees you'll find the shortest combination if it exists, but it's not very efficient.

Here's how the algorithm would work step-by-step:

Start by trying to cover the target video using just one video clip. Check if this single clip covers the entire duration.
If one clip isn't enough, try all possible combinations of two clips. See if any of these pairs cover the target duration completely.
If two clips aren't enough, try all possible combinations of three clips, four clips, and so on.
For each combination of clips, check if they can be stitched together to cover the whole target video length without any gaps or overlaps.
Keep track of every successful combination that covers the full duration.
Once you've tried all possible combinations up to using all available video clips, compare the successful combinations you found.
Choose the combination that uses the fewest video clips. That's your solution.

Code Implementation

def video_stitching_brute_force(clips, time):    number_of_clips = len(clips)
    minimum_clips_needed = float('inf')
    
    for clips_to_use in range(1, number_of_clips + 1):
        # Iterate through all combinations of clips to find the minimum to stitch
        from itertools import combinations
        for combination in combinations(clips, clips_to_use):
            current_time = 0
            combination_successful = True
            
            # Sort the selected clips based on their start time
            sorted_combination = sorted(combination, key=lambda clip: clip[0])
            
            if sorted_combination[0][0] > 0:
                combination_successful = False
            else:
                current_time = sorted_combination[0][1]
            
            # Check if the current combination covers the entire duration
            for i in range(1, len(sorted_combination)):
                if sorted_combination[i][0] > current_time:
                    combination_successful = False
                    break
                current_time = max(current_time, sorted_combination[i][1])
            
            if combination_successful:
                # If clips cover the entire duration and are less than current min, update it
                if current_time >= time:
                    minimum_clips_needed = min(minimum_clips_needed, clips_to_use)
    
    if minimum_clips_needed == float('inf'):
        return -1
    else:
        return minimum_clips_needed

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach involves exploring all possible combinations of video clips. In the worst case, we might need to consider every subset of the input clips to see if they can cover the target video duration. Since a set of n clips has 2^n possible subsets (combinations), the time complexity is exponential, specifically O(2^n). This stems from the need to check every possible combination, regardless of whether it is viable or not. The algorithm's runtime grows exponentially as the number of video clips, 'n', increases.

Space Complexity

O(2^N) – The brute force approach explores all possible combinations of video clips. In the worst-case scenario, where N is the number of video clips, the algorithm may need to store up to 2^N combinations (subsets) of clips temporarily while checking if they cover the target video length. Although not explicitly mentioned as a stored data structure in the prompt, the recursive or iterative exploration of all subsets requires implicitly remembering which clips are in the current subset being considered, which can grow exponentially with the number of clips. Therefore the space complexity is O(2^N).

Optimal Solution

Approach

The goal is to cover a complete video using the fewest possible clips. We sort the clips to make the best decision about which clip to use next, always prioritizing the clip that extends our coverage the furthest.

Here's how the algorithm would work step-by-step:

First, organize the video clips based on their starting times.
Begin at time zero (the start of the video).
Look through the clips to find all that start at or before your current time.
Among these clips, pick the one that stretches furthest into the video.
Move your current time forward to the end time of the clip you just picked.
Repeat the process: find clips starting at or before your new current time, and pick the one that goes furthest.
Keep going until you've covered the entire video length, or until you find you can't reach the end.
If you reach the end of the video, count how many clips you used. If you can't reach the end, it's impossible to stitch the video together.

Code Implementation

def video_stitching(clips, time):    clips.sort()
    reachable_time = 0
    number_of_clips = 0
    current_reach = 0
    index = 0
    
    # Iterate as long as we haven't covered the entire video.    while reachable_time < time:
        max_reach = reachable_time
        # Find the clip that extends current reach the furthest.        while index < len(clips) and clips[index][0] <= reachable_time:
            max_reach = max(max_reach, clips[index][1])
            index += 1
        
        # If we can't extend current reach, it's impossible.        if max_reach == reachable_time:
            return -1
            
        reachable_time = max_reach
        number_of_clips += 1
        
    return number_of_clips

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is sorting the input clips based on their start times. Sorting algorithms typically have a time complexity of O(n log n), where n is the number of clips. After sorting, we iterate through the clips to find the optimal stitching, which takes O(n) in the worst case since we look at each clip at most once. Because O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm primarily involves sorting the input clips and iterating through them. While sorting might use space depending on the algorithm (e.g., merge sort is O(N)), the provided description doesn't explicitly state that sorting is done in-place. However, the *core* logic described, after sorting, involves maintaining a few variables like the current time and the number of clips used. No auxiliary data structures that scale with the input size (N, representing the number of clips) are used to store intermediate results or track visited clips, thus the space is constant. Therefore the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty clips array	Return -1 immediately as no stitching is possible without clips.
Target time is zero	Return 0 immediately as no clips are needed to cover zero time.
No clip starts at time 0	Return -1 immediately as the target time cannot be reached if no clips start from time 0.
Clips do not cover the entire range up to the target time	Return -1 because it's impossible to stitch a video to the target time.
Single clip covers the entire target time	Return 1, indicating only one clip is required.
Very large number of clips with small durations	Ensure the solution has reasonable time complexity (e.g., O(n log n) or O(n)) and avoids excessive iterations or memory allocation.
Clips are overlapping with each other	The algorithm should still function correctly and find the minimal number of clips despite overlapping intervals, potentially even leveraging the overlaps.
Target time is smaller than the start time of any clip	If target is smaller than the smallest start time, return -1 since stitching to that target is impossible.