1024. Video Stitching LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 1024. Video Stitching LeetCode Solution with the best time and space complexity. The solution to Video Stitching problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Video Stitching solution in C++
Video Stitching solution in Java
Video Stitching solution in Python
Additional Resources

1024. Video Stitching LeetCode Solution image

Problem Statement of Video Stitching

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] = [starti, endi] indicates that the ith clip started at starti and ended at endi.
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 <= starti <= endi <= 100
1 <= time <= 100

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(1)

1024. Video Stitching LeetCode Solution in C++

class Solution {
 public:
  int videoStitching(vector<vector<int>>& clips, int time) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    ranges::sort(clips.begin(), clips.end());

    int i = 0;
    while (farthest < time) {
      while (i < clips.size() && clips[i][0] <= end)
        farthest = max(farthest, clips[i++][1]);
      if (end == farthest)
        return -1;
      ++ans;
      end = farthest;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1024. Video Stitching LeetCode Solution in Java

class Solution {
  public int videoStitching(int[][] clips, int time) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    Arrays.sort(clips, (a, b) -> Integer.compare(a[0], b[0]));

    int i = 0;
    while (farthest < time) {
      while (i < clips.length && clips[i][0] <= end)
        farthest = Math.max(farthest, clips[i++][1]);
      if (end == farthest)
        return -1;
      ++ans;
      end = farthest;
    }

    return ans;
  }
}
// code provided by PROGIEZ

1024. Video Stitching LeetCode Solution in Python

class Solution:
  def videoStitching(self, clips: list[list[int]], time: int) -> int:
    ans = 0
    end = 0
    farthest = 0

    clips.sort()

    i = 0
    while farthest < time:
      while i < len(clips) and clips[i][0] <= end:
        farthest = max(farthest, clips[i][1])
        i += 1
      if end == farthest:
        return -1
      ans += 1
      end = farthest

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents