Problem statement

https://leetcode.com/problems/video-stitching/

Solution

This problem is about what is minimum number of intervals we need to cover given range. It is simpler version of Leetcode 1326. Minimum Number of Taps to Open to Water a Garden. One possible solution is greedy. What we need to do is:

  1. Sort intervals, where we cut values > n.
  2. Also check that we reached point n in the end, because in taps problem there were n + 1 taps.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def videoStitching(self, clips, n):
        clips = sorted([(i, min(n, j)) for i, j in clips])
        ans, r, i = 0, 0, 0

        while i < len(clips) and r < n:
            r2 = r
            while i < len(clips) and clips[i][0] <= r:
                r2 = max(r2, clips[i][1])
                i += 1
            
            if r2 == r != n: return -1        
            ans, r = ans + 1, r2 
            
        return ans if r == n else -1