Code Implementation

class Solution:
    def videoStitching(self, clips, time):
        clips.sort()
        res = 0
        curr_end = 0
        next_end = 0
        i = 0
        n = len(clips)
        while curr_end < time:
            while i < n and clips[i][0] <= curr_end:
                next_end = max(next_end, clips[i][1])
                i += 1
            if curr_end == next_end:
                return -1
            res += 1
            curr_end = next_end
        return res
      

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        sort(clips.begin(), clips.end());
        int res = 0, curr_end = 0, next_end = 0, i = 0, n = clips.size();
        while (curr_end < time) {
            while (i < n && clips[i][0] <= curr_end) {
                next_end = max(next_end, clips[i][1]);
                i++;
            }
            if (curr_end == next_end) return -1;
            res++;
            curr_end = next_end;
        }
        return res;
    }
};
      

import java.util.*;
class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, (a, b) -> a[0] - b[0]);
        int res = 0, curr_end = 0, next_end = 0, i = 0, n = clips.length;
        while (curr_end < time) {
            while (i < n && clips[i][0] <= curr_end) {
                next_end = Math.max(next_end, clips[i][1]);
                i++;
            }
            if (curr_end == next_end) return -1;
            res++;
            curr_end = next_end;
        }
        return res;
    }
}
      

var videoStitching = function(clips, time) {
    clips.sort((a, b) => a[0] - b[0]);
    let res = 0, curr_end = 0, next_end = 0, i = 0, n = clips.length;
    while (curr_end < time) {
        while (i < n && clips[i][0] <= curr_end) {
            next_end = Math.max(next_end, clips[i][1]);
            i++;
        }
        if (curr_end === next_end) return -1;
        res++;
        curr_end = next_end;
    }
    return res;
};
      

Problem Description

• You can use any clip any number of times (no need to worry about reusing elements).
• There may be overlap between clips.
• Each clip is an interval [start, end] with 0 <= start < end <= 100.
• The number of clips is between 1 and 100.
• There is no guarantee that a solution exists.

Thought Process

Solution Approach

1. Sort the Clips: First, sort the clips array by their start time. This allows us to process them in order and makes it easier to find which clips can extend the current coverage.
2. Initialize Variables:
   • curr_end: The end of the interval we've currently covered.
   • next_end: The furthest point we can reach from the current position using available clips.
   • res: The count of clips used so far.
   • i: Index to iterate through the sorted clips.
3. Main Loop: While curr_end is less than time:
   • For all clips that start at or before curr_end, update next_end to the maximum of their end values. This finds the best possible extension from the current coverage.
   • If next_end does not advance beyond curr_end, it means there is a gap and it's impossible to cover the interval. Return -1.
   • Otherwise, increment the clip count (res) and set curr_end to next_end.
4. Return the Result: Once the loop ends, return res as the minimum number of clips needed.

Example Walkthrough

1. Sort the clips: [[0,2],[1,5],[1,9],[4,6],[5,9],[8,10]]
2. Start with curr_end = 0, next_end = 0, res = 0, i = 0
3. First iteration:
   • Clip [0,2] starts at 0, so update next_end = 2 (i=1).
   • No more clips with start ≤ 0. Since next_end > curr_end, increment res = 1, set curr_end = 2.
4. Second iteration:
   • Clips [1,5] and [1,9] both start ≤ 2. Update next_end to 9 (max of 5 and 9). (i=3)
   • No more clips with start ≤ 2. Increment res = 2, set curr_end = 9.
5. Third iteration:
   • Clips [4,6], [5,9] start ≤ 9. Update next_end to 9 (no further extension here). (i=5)
   • Clip [8,10] starts ≤ 9. Update next_end to 10. (i=6)
   • Increment res = 3, set curr_end = 10.
6. curr_end is now 10, so the interval is covered. The answer is 3.

Time and Space Complexity

• Brute-force approach:
  • Would involve trying all possible combinations of clips, which is exponential time: O(2^N), where N is the number of clips.
  • Space complexity would also be high due to recursion or storing all subsets.
• Optimized greedy approach (current solution):
  • Sorting the clips takes O(N log N).
  • The main loop iterates over the clips at most once: O(N).
  • Total time complexity: O(N log N).
  • Space complexity is O(1) (ignoring the space used to store the input).

Summary