Video Stitching

• Create an integer array dp of size time + 1 to store the minimum number of clips to cover the interval [0, i].
• Initialize dp[0] to 0 and all other elements dp[i] to a value representing infinity (e.g., time + 2, which is larger than any possible valid answer).
• Iterate i from 1 to time. For each i, we want to compute dp[i].
• Inside this loop, iterate through all available clips [start, end].
• If a clip can cover the time point i (i.e., start < i <= end), it means we can potentially use this clip. To do so, we must have already covered the interval [0, start]. The cost for that is dp[start].
• So, we can update dp[i] with min(dp[i], dp[start] + 1).
• After checking all clips for the current i, dp[i] will hold the minimum clips to cover [0, i].
• After the loops complete, if dp[time] is still the infinity value, it means [0, time] cannot be covered. Return -1.
• Otherwise, dp[time] holds the minimum number of clips, so return it.

We define dp[i] as the minimum number of clips needed to create a continuous video from time 0 to time i. The size of our dp array will be time + 1.

The base case is dp[0] = 0, as it takes zero clips to cover a duration of zero. All other dp[i] values are initialized to a large number (like time + 2) to signify that they are not yet reachable.

We then iterate from i = 1 to time. For each i, we try to find the best way to cover the interval [0, i]. We can do this by considering every clip [start, end]. If a clip covers the time point i (i.e., start < i <= end), it can be the last clip in our sequence. If we choose this clip, we must have already covered the interval [0, start]. The number of clips to do that is dp[start]. Therefore, the total number of clips would be dp[start] + 1. We take the minimum over all such possible clips.

The final answer is dp[time]. If dp[time] remains at its initial large value, it means the interval [0, time] is impossible to cover.

1import java.util.Arrays;2 3class Solution {4    public int videoStitching(int[][] clips, int time) {5        int[] dp = new int[time + 1];6        // Initialize dp array with a value larger than any possible answer.7        // time + 2 is a safe choice since the max answer can be time + 1.8        Arrays.fill(dp, time + 2);9        dp[0] = 0;10 11        for (int i = 1; i <= time; i++) {12            for (int[] clip : clips) {13                int start = clip[0];14                int end = clip[1];15                if (start < i && i <= end) {16                    // If this clip can cover time i, we check the cost to cover up to its start time.17                    if (dp[start] != time + 2) {18                        dp[i] = Math.min(dp[i], dp[start] + 1);19                    }20                }21            }22        }23 24        return dp[time] == time + 2 ? -1 : dp[time];25    }26}

• First, sort the clips array based on their start times. This allows us to process clips in an orderly fashion.
• Initialize count = 0 (number of clips used), current_end = 0 (the farthest point covered so far), and i = 0 (an index to traverse the sorted clips).
• Enter a loop that continues as long as current_end < time.
• Inside the loop, we are trying to make one greedy choice. We first find the maximum possible reach (next_end) from the current position.
• To do this, we scan through all clips that can extend our current coverage, i.e., all clips clips[j] where clips[j][0] <= current_end. We use the index i to avoid re-scanning clips.
• We update next_end to be the maximum end time among these candidate clips.
• After scanning all eligible clips, if next_end has not increased (i.e., next_end == current_end), it means we are stuck and cannot cover the full duration. Return -1.
• If we can extend our coverage, we increment count and update current_end = next_end.
• The loop continues until current_end covers time.
• Finally, return count.

We start by sorting the clips by their start times. This helps in efficiently finding the next clip to extend our coverage.

We maintain a variable current_end representing the farthest point in time we have covered, initialized to 0. We also have a count for the number of clips used. The process is iterative: in each step, we select one clip.

While our current_end is less than time, we look for the best next clip. We iterate through the sorted clips that start at or before our current_end. Among all such clips, we find the one that reaches the farthest (has the maximum end time). Let's call this maximum reach next_end.

If, after checking all relevant clips, next_end is no better than current_end, it means we're stuck in a gap and cannot proceed. In this case, it's impossible to cover the entire [0, time] interval, so we return -1.

Otherwise, we have successfully extended our coverage. We increment our count by one (for the clip we just chose) and update current_end to next_end. We repeat this process until current_end reaches or exceeds time.

1import java.util.Arrays;2 3class Solution {4    public int videoStitching(int[][] clips, int time) {5        // Sort clips by start time, then by end time in descending order for a slight optimization.6        Arrays.sort(clips, (a, b) -> {7            if (a[0] != b[0]) {8                return a[0] - b[0];9            } else {10                return b[1] - a[1];11            }12        });13 14        int count = 0;15        int current_end = 0;16        int i = 0;17        int n = clips.length;18 19        while (current_end < time) {20            int next_end = current_end;21            // Find the clip that starts at or before current_end and extends the furthest.22            while (i < n && clips[i][0] <= current_end) {23                next_end = Math.max(next_end, clips[i][1]);24                i++;25            }26 27            // If we couldn't extend our reach, it's impossible.28            if (next_end == current_end) {29                return -1;30            }31 32            // We've chosen one more clip.33            count++;34            current_end = next_end;35        }36 37        return count;38    }39}

• Create an array max_reach of size time + 1. max_reach[s] will store the maximum end time of any clip starting at time s.
• Iterate through all clips [start, end]. For each clip, if start <= time, update max_reach[start] = max(max_reach[start], end). This pre-processing step takes O(N) time.
• Initialize count = 0, current_end = 0 (farthest reach with count clips), and next_end = 0 (farthest reach with count + 1 clips).
• Iterate with a variable i from 0 up to time - 1.
• In each iteration, update next_end with the maximum possible reach from time i: next_end = max(next_end, max_reach[i]).
• If the iterator i reaches the boundary of our current coverage (i == current_end), it signifies that we must use a new clip to go further. This is a "jump".
• When we jump (at i == current_end), we increment count and update current_end to the new next_end we've calculated.
• If at the point of a jump, current_end has not advanced (i == next_end), it means we are stuck and cannot reach time. Return -1.
• If at any point current_end becomes greater than or equal to time, we have successfully covered the interval, and we can return the current count.
• If the loop finishes and we still haven't covered time, it's impossible. Return -1.

The core idea is to transform the input clips into a more accessible format. We create an array, max_reach, of size time + 1. We populate this array by iterating through the clips: for each clip [start, end], we set max_reach[start] = max(max_reach[start], end). After this O(N) pre-processing step, max_reach[i] tells us the farthest we can get if we start a clip at time i.

With this max_reach array, we can find the solution in a single pass from i = 0 to time. We maintain two pointers: current_end, the farthest we can reach with the clips selected so far, and next_end, the farthest we can reach by adding one more clip. Both are initialized to 0.

We loop from i = 0 to time - 1. In each step i, we update next_end = max(next_end, max_reach[i]). This means we are checking all possible new clips that start within our current reach and finding the one that goes the farthest.

When our loop variable i reaches current_end, it means we've reached the limit of our current clip's coverage. We must take a "jump" by selecting the best clip we've found so far. We increment our clip count and set current_end to the next_end. If current_end hasn't improved, we're stuck and return -1. If the new current_end covers time, we're done and can return the count.

1class Solution {2    public int videoStitching(int[][] clips, int time) {3        if (time == 0) {4            return 0;5        }6        // max_reach[i] stores the maximum end time of a clip starting at i.7        int[] max_reach = new int[time + 1];8        for (int[] clip : clips) {9            if (clip[0] <= time) {10                max_reach[clip[0]] = Math.max(max_reach[clip[0]], clip[1]);11            }12        }13 14        int count = 0;15        int current_end = 0;16        int next_end = 0;17 18        for (int i = 0; i < time; i++) {19            // Update the farthest reach possible from the current position.20            next_end = Math.max(next_end, max_reach[i]);21 22            // If we are at the end of the current clip's coverage.23            if (i == current_end) {24                // If we can't move forward, it's impossible.25                if (i == next_end) {26                    return -1;27                }28                // Take the jump.29                count++;30                current_end = next_end;31                // If the new reach covers the target time, we are done.32                if (current_end >= time) {33                    return count;34                }35            }36        }37 38        return -1; // Should be covered by the check inside the loop.39    }40}