Video Stitching - Leetcode Solution

Video stitching is the process of combining multiple video clips into a single video. In the Video Stitching problem on leetcode, we are given a list of video clips and their start and end times. We need to find the minimum number of clips required to stitch together the entire video and return -1 if it is not possible.

To solve this problem, we can use the greedy approach. We can sort the video clips by their starting time and then iterate over them. For each iteration, we will find the video clip which ends farthest and has the starting time less than or equal to the end time of the current clip. We will add this clip to the stitched video and continue iterating until we reach the end time of the video.

If at any point, we are unable to find a clip to extend the current stitched video, it means that it is not possible to stitch the entire video. In this case, we will return -1.

Here is the implementation of the algorithm in Python:

def videoStitching(clips, T):
    # Sort the clips by their starting time
    clips.sort()

    # Initialize the variables
    end_time = 0
    stitched_video = []
    clip_count = 0

    # Iterate over the clips
    for clip_start, clip_end in clips:
        # If the current clip starts after the end time, return -1
        if clip_start > end_time:
            return -1

        # If the current clip can extend the stitched video
        if clip_end > end_time:
            # Add this clip to the stitched video
            stitched_video.append((clip_start, clip_end))
            # Update the end time
            end_time = clip_end
            # Increment the clip count
            clip_count += 1

        # If we have stitched the entire video, return the clip count
        if end_time >= T:
            return clip_count

    # If we have not stitched the entire video, return -1
    return -1

In the above code, we first sort the video clips by their starting time. We then initialize the variables end_time, stitched_video, and clip_count to 0.

We then iterate over the clips and for each clip, we check if its starting time is greater than the current end_time. If it is, it means that there is a gap in the stitched video and we cannot stitch the remaining video. In this case, we return -1.

If the starting time of the current clip is less than or equal to the end_time, we check if its end time is greater than the current end_time. If it is, we add this clip to the stitched video and update the end_time to the end time of this clip.

We also increment the clip_count variable to keep track of the number of clips used to stitch the video. Finally, we check if we have stitched the entire video and if we have, we return the clip count. If we have not stitched the entire video, we return -1.

The time complexity of this algorithm is O(nlogn) due to the sorting operation. The space complexity is O(n) because we store the stitched video and the clip count.

1