1024. Video Stitching

MediumGreedyArrayDynamic Programming
Leetcode Link

Problem Description

You are tasked with the challenge of creating a highlight reel from a series of overlapping video clips taken during a sporting event. The entire event has a duration of time seconds. The video clips are provided in the form of a list, where each clip is represented by a pair of numbers: the start time (start_i) and the end time (end_i). The clips may overlap and can have different lengths. Interestingly, you have the freedom to cut these clips into any number of segments you wish.

The main objective is to find the smallest number of clips necessary to cover the entire duration of the event from 0 to time seconds. If it is not possible to cover the entire event with the given clips, the function should return -1.

Intuition

To solve this problem, we first need to think about how to use the given clips to cover the entire time span of the event. A brute force approach might try to consider all possible combinations of clips, but this would be highly inefficient. Instead, we need a smarter strategy that can quickly determine the optimal set of clips without redundant computations.

The intuition behind the solution is to first figure out, for each second in the event's duration, what is the furthest point we can reach if we were to start a clip at that second. We begin by initializing an array that will hold this information. As we iterate through each clip, we record the farthest end time we can achieve, starting from each start time that is less than time.

Next, we iterate through each second in the event, extending our reach as we find greater end times. The goal is to keep extending our current segment's end time (pre) until we can no longer do so or until we reach the end of the event. If at any point, the farthest reach (mx) is less than or equal to the current second, it means there is a gap in the coverage and hence the task is impossible.

On the other hand, when the current second reaches the previous maximum reach (pre), it indicates that we have utilized a clip to its fullest extent, and we need to select another clip to extend our coverage. This selection increments our answer to the minimum number of clips needed. Eventually, if we are able to cover the whole event, we return the number of clips used; otherwise, if we encounter a coverage gap, we return -1.

This strategy is efficient because it takes advantage of the greedy approach, always picking the clip that extends coverage the furthest at each step, and ensuring that a minimum number of clips are used. The algorithm will sweep through the time units only once, maintaining the maximum reach and updating the number of clips used as needed.

Learn more about Greedy and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which of the following is a min heap?

Solution Approach

The solution involves a greedy algorithm that aims to extend the reach of the current clip segment as far as possible within the given time. Let's walk through the implementation:

  • First, we initialize a list called last with a length equal to the time. This list is used to track the furthest end time (last[a]) that can be reached from each starting second a.

  • The solution iterates over each clip [a, b] from the provided clips list. For each clip, it checks if the start time a is within the event duration (a < time). If so, it updates last[a] with the maximum of its current value and the end time b of the current clip. This step effectively finds the furthest end time achievable from each start time.

1last = [0] * time
2for a, b in clips:
3    if a < time:
4        last[a] = max(last[a], b)

  • We then initialize three variables: ans to keep track of the number of clips used, mx to store the furthest end time reachable at any point, and pre which represents the end of the current clip segment we are creating.

  • The next loop goes through each second (index i) in the last list, updating mx to the maximum of its current value and last[i] which represents the furthest time we can reach from second i. Here are two important conditions:

    • If at any point mx (the maximum reach so far) is less than or equal to the current second i, this means that there is a gap in our clip coverage and we cannot create a continuous highlight reel up to this second. Hence, we return -1.

    • If the current second i equals pre (the previous segment's farthest reach), it means that we need to start a new segment by selecting another clip. We increment ans (the number of clips used), and update pre to mx to reflect the new segment's farthest reach.

1ans = mx = pre = 0
2for i, v in enumerate(last):
3    mx = max(mx, v)
4    if mx <= i:
5        return -1
6    if pre == i:
7        ans += 1
8        pre = mx
  • After the loop is completed, if we are able to reach the end of the event's duration (time), the variable ans will hold the minimum number of clips needed. The function returns this value.

This approach uses a greedy algorithm for selecting clips, as well as dynamic programming techniques to efficiently calculate the maximum coverage at each point in time. By continuously updating the furthest reach and tracking the number of clips, the algorithm ensures that it always progresses towards the goal and only uses the necessary clips to cover the entire event duration.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have an event that lasts for 10 seconds (time = 10), and we have the following video clips provided in the form of (start_i, end_i) pairs:

1Clips = [(0, 3), (1, 5), (4, 8), (7, 10)]

Following the solution approach:

  1. Initialize the last list with a length equal to time (which is 10 in this case), to track the furthest end time we can reach from each starting second.

    1last = [0]*10  # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

  2. Iterate through each clip to update the last list.

    • For clip (0, 3), since 0 < 10, update last[0] to 3.
    • For clip (1, 5), since 1 < 10, update last[1] to 5.
    • For clip (4, 8), since 4 < 10, update last[4] to 8.
    • For clip (7, 10), since 7 < 10, update last[7] to 10.

    After iterating, last looks like this:

    1last = [3, 5, 0, 0, 8, 0, 0, 10, 0, 0]

  3. Initialize ans (the number of clips used), mx (the farthest end time reachable at any point), and pre (the end of the current clip segment) to 0.

  4. Iterate through the last list to find the minimum number of clips:

    • For i = 0, mx becomes max(0, 3), so mx = 3.
    • For i = 1, mx becomes max(3, 5), so mx = 5.
    • Since i has not reached pre yet, we continue without incrementing ans.
    • For i = 2, mx remains 5 as last[2] is 0 and 5 > 2.
    • ...
    • When i = 3 and pre = 3, we find our first segment covering from second 0 to second 5. Increment ans to 1, and update pre to mx (5).
    • Continue this process until i=7.
    • For i = 7, mx becomes max(5, 10), so mx = 10.
    • i = 7 is equal to pre which is 5, so increment ans to 2, and update pre to mx (10).
    • We now have covered the duration from 0 to 10 seconds with 2 segments.

  5. Finally, since the last list has been fully traversed and we've been able to cover every second up to the end of the event (10), we conclude that 2 is the minimum number of clips needed to cover the event.

Following this example, the function would return 2 since we can cover the entire event with the [(1, 5), (7, 10)] clips.

Solution Implementation

1from typing import List
2
3class Solution:
4    def videoStitching(self, clips: List[List[int]], target_time: int) -> int:
5        # Initialize a list to keep track of the furthest point each second can reach
6        furthest_reach = [0] * target_time
7      
8        # Pre-process the clips to fill in the furthest_reach list
9        for start, end in clips:
10            # Only consider clips that start before the target_time
11            if start < target_time:
12                # Update the furthest_reach for the second that this clip starts
13                furthest_reach[start] = max(furthest_reach[start], end)
14      
15        clips_required = 0  # Counter for the minimum number of clips required
16        current_end = 0     # The furthest point we can reach without adding another clip
17        next_end = 0        # The furthest point we can reach by including another clip
18      
19        # Iterate through each second up to the target_time
20        for second in range(target_time):
21            # Determine the most distant point in time we can reach from this second
22            next_end = max(next_end, furthest_reach[second])
23          
24            # If the next_end is less or equal to the current second, it means we have a gap.
25            # We can't reach the current second from any previous clips.
26            if next_end <= second:
27                return -1
28          
29            # When the current second reaches the current_end, we need to select a new clip
30            if current_end == second:
31                clips_required += 1
32                # Update current_end to the furthest point reachable from this clip
33                current_end = next_end
34
35        return clips_required
36
37# Example Usage
38solution = Solution()
39clips = [[0,2], [4,6], [8,10], [1,9], [1,5], [5,9]]
40target_time = 10
41print(solution.videoStitching(clips, target_time))  # Outputs the minimum number of clips needed
42
1class Solution {
2    public int videoStitching(int[][] clips, int T) {
3        int[] maxReach = new int[T];
4      
5        // Iterate over each clip and record the furthest end time for each start time
6        for (int[] clip : clips) {
7            int start = clip[0], end = clip[1];
8            if (start < T) {
9                maxReach[start] = Math.max(maxReach[start], end);
10            }
11        }
12      
13        int count = 0; // the minimum number of clips needed
14        int maxEnd = 0; // the farthest end time we can reach so far
15        int prevEnd = 0; // the end time of the last clip we have included in the solution
16      
17        // Loop through each time unit up to T
18        for (int i = 0; i < T; i++) {
19            maxEnd = Math.max(maxEnd, maxReach[i]);
20          
21            // If the maxEnd we can reach is less or equal to current time 'i',
22            // it is impossible to stitch the video up to 'i'
23            if (maxEnd <= i) {
24                return -1;
25            }
26          
27            // When we reach the end of the previous clip, increment the count of clips
28            // and set the prevEnd to maxEnd to try and reach further in the next iteration
29            if (prevEnd == i) {
30                count++;
31                prevEnd = maxEnd;
32            }
33        }
34      
35        // Return the minimum number of clips needed
36        return count;
37    }
38}
39
1class Solution {
2public:
3    int videoStitching(vector<vector<int>>& clips, int time) {
4        // lastSeen represents the farthest time we can get to starting from each second
5        vector<int> lastSeen(time, 0);
6      
7        // Iterate through the clips and fill up the lastSeen vector with the farthest end time
8        // for clips that start at or before 'i' and are relevant to our goal (i.e., within 'time').
9        for (auto& clip : clips) {
10            int start = clip[0], end = clip[1];
11            if (start < time) {
12                lastSeen[start] = max(lastSeen[start], end);
13            }
14        }
15      
16        // 'maxReach' holds the farthest time we can reach at any moment
17        int maxReach = 0;
18        // 'answer' is the minimum number of clips needed to cover [0, time)
19        int answer = 0;
20        // 'previous' holds the end time of the last selected clip
21        int previous = 0;
22      
23        // Iterate from 0 to time to determine if we can reach 'time' and what minimum number of clips are needed
24        for (int i = 0; i < time; ++i) {
25            // Extend the maxReach if the current second allows for a farther reach
26            maxReach = max(maxReach, lastSeen[i]);
27          
28            // If maxReach is less or equal to 'i', it means we can't move past this second, thus return -1
29            if (maxReach <= i) {
30                return -1;
31            }
32          
33            // If 'i' equals 'previous', it means we've used one clip and need to select the next
34            // The selection is based on how far we can reach from here (maxReach)
35            if (previous == i) {
36                ++answer; // Increment the number of clips used
37                previous = maxReach; // Update 'previous' to be the farthest time we can reach now
38            }
39        }
40      
41        // Return the minimum number of clips needed
42        return answer;
43    }
44};
45
1// Defines the type for a video clip, which is an array of 2 numbers
2type Clip = [number, number];
3
4// Initializes an array to represent the farthest time reachable starting from each second
5let lastSeen: number[] = [];
6
7// Calculates the minimum number of clips required to cover a range from 0 to time
8// clips: an array of video clips defined by their start and end times
9// time: the total time that needs to be covered by the clips
10function videoStitching(clips: Clip[], time: number): number {
11    // Reset the lastSeen array for the current computation
12    lastSeen = Array(time).fill(0);
13
14    // Populate the lastSeen array with the furthest end time for relevant clips
15    for (let clip of clips) {
16        let [start, end] = clip;
17        if (start < time) {
18            lastSeen[start] = Math.max(lastSeen[start], end);
19        }
20    }
21
22    // Variables to track the farthest time we can reach and the minimum clips needed
23    let maxReach = 0;
24    let answer = 0;
25    let previousReach = 0;
26
27    // Iterate through each second until time to compute the minimum number of clips required
28    for (let i = 0; i < time; i++) {
29        // Extend the maxReach with the furthest time we can achieve from this second
30        maxReach = Math.max(maxReach, lastSeen[i]);
31
32        // If we cannot progress beyond this second, return -1 to indicate it's impossible
33        if (maxReach <= i) {
34            return -1;
35        }
36
37        // If we've reached the end of the current clip, select the next clip
38        if (previousReach == i) {
39            answer++;
40            previousReach = maxReach; // Update our reach to the furthest end time encountered
41        }
42    }
43
44    // Return the calculated minimum number of clips needed
45    return answer;
46}
47
Not Sure What to Study? Take the 2-min Quiz

Which two pointer technique does Quick Sort use?

Time and Space Complexity

Time Complexity

The provided Python code has a for loop that iterates through the clips list, which has a length that we can refer to as n. Inside this loop, we have constant time operations (if comparison and max function), meaning that this part of the algorithm has a time complexity of O(n).

Following that, there is another for loop which iterates through the last list. Since last has a length equal to the time parameter, this loop iterates time times. Once again, we perform constant time operations within the loop (max function, if comparisons, and simple assignments).

Therefore, the second loop has a time complexity of O(time). Since these two loops are not nested but executed in sequence, the overall time complexity of the code combines both complexities, resulting in O(n + time).

Space Complexity

For space complexity, the code allocates an array last of length equal to time, which requires O(time) space. The rest of the variables used in the code (ans, mx, and pre) require constant space, O(1).

Therefore, the overall space complexity of the function is O(time) because this is the largest space requirement that does not change with different inputs of clips.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«