< Back




1024. Video Stitching

We're given an array of intervals, (start, end), and a time. We're asked to find the minimum number
of intervals we can use in this array to cover 0 - time. This is a regular greedy algorithm
question.

We start by sorting the input with a compound key - we'll sort based on start time, but also sort
end time in decreasing order. We want to start filling in the time from 0, but we also want to pick
intervals that cover the most time from start to end. We keep track of the most recently seen and
greatest end time.

We start popping from the clips list. We remove all clips that have an end time less than or equal
to the greatest end we've seen so far. We already cover those time slots, why would we keep those
intervals?

For all the clips that have a start time less than or equal to the greatest end we've seen so far,
we find the clip with the greatest end time - this will cover the most time as we stitch the video
together. If we can't find a next greater end time, and we still have clips leftover, that means
that we have time missing in our clip intervals - so we can't stitch everything together. We return
-1 in this case.

We update the new greatest end time, and increment our answer by 1 to note we've chosen an interval.
If the greatest end time recorded is ever greater than or equal to our target end time, we return
the number of intervals chosen.

The solution is as follows:


  class Solution:
      def videoStitching(self, clips: List[List[int]], time: int) -> int:
          clips.sort(key=lambda x: (x[0], -x[1]))
          end = ans = 0
          next_end = float("-inf")

          while clips:
              while clips and clips[0][1] <= end:
                  clips.pop(0)

              while clips and clips[0][0] <= end:
                  next_end = max(next_end, clips.pop(0)[1])

              if next_end == end and clips:
                  return -1

              end = next_end
              ans += 1

              if end >= time:
                  return ans

          return -1


_ Time Complexity:

  O(n log(n)) - We have to sort the input.

_ Space Complexity:

  O(n) - Python sorting takes O(n) space.


Alternative counting sort answer with O(n) time and O(n) space:


  class Solution:
      def videoStitching(self, clips: List[List[int]], time: int) -> int:
          max_length = [0] * (time + 1)

          for i in range(len(clips)):
              start, end = max(0, min(time, clips[i][0])), min(time, clips[i][1])
              max_length[start] = max(max_length[start], end)

          ans = curr_end = next_end = 0

          for i in range(time + 1):
              if i > next_end:
                  return -1

              if i > curr_end:
                  ans += 1
                  curr_end = next_end

              next_end = max(next_end, max_length[i])

          return ans