Solution Explanation:

The problem asks for the minimum number of video clips needed to cover the entire duration of a sporting event from time 0 to time. Each clip is represented by a start and end time. We can cut clips into smaller segments, but the goal is to minimize the total number of clips used.

The optimal approach is a greedy algorithm. The core idea is to iteratively select the clip that extends the furthest to the right, ensuring maximal coverage with each selection. This avoids unnecessary overlapping or inefficient choices.

Algorithm:

1. Preprocessing: Create an array last of size time. For each clip [start, end], update last[start] to be the maximum of its current value and end. This array helps to quickly find the clip with the longest reach starting from a particular time.

2. Greedy Selection:

   • Initialize ans (number of clips), mx (maximum reachable time), and pre (reach of the previously selected clip) to 0.
   • Iterate from i = 0 to time -1:
     • Update mx to be the maximum of mx and last[i]. This represents the furthest we can currently reach.
     • If mx <= i, it means we can't cover the time interval, so return -1 (impossible).
     • If pre == i, it signifies that we need a new clip because we've reached the limit of the previous one. Increment ans, and update pre to the new maximum reach mx.

3. Return Result: After iterating through all times, return ans.

Time and Space Complexity:

• Time Complexity: O(n + m), where n is the number of clips and m is the value of time. The preprocessing step takes O(n) time, and the greedy selection step takes O(m) time.

• Space Complexity: O(m). We use an array last of size m to store the maximum reach for each time point.

Code Implementation:

The code implementations below follow the algorithm described above. Note that minor variations exist across languages due to syntax differences, but the core logic remains the same.

Python3:

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        last = [0] * time
        for a, b in clips:
            if a < time:
                last[a] = max(last[a], b)
        ans = mx = pre = 0
        for i, v in enumerate(last):
            mx = max(mx, v)
            if mx <= i:
                return -1
            if pre == i:
                ans += 1
                pre = mx
        return ans
 

Java:

class Solution {
    public int videoStitching(int[][] clips, int time) {
        int[] last = new int[time];
        for (var e : clips) {
            int a = e[0], b = e[1];
            if (a < time) {
                last[a] = Math.max(last[a], b);
            }
        }
        int ans = 0, mx = 0, pre = 0;
        for (int i = 0; i < time; ++i) {
            mx = Math.max(mx, last[i]);
            if (mx <= i) {
                return -1;
            }
            if (pre == i) {
                ++ans;
                pre = mx;
            }
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> last(time);
        for (auto& v : clips) {
            int a = v[0], b = v[1];
            if (a < time) {
                last[a] = max(last[a], b);
            }
        }
        int mx = 0, ans = 0;
        int pre = 0;
        for (int i = 0; i < time; ++i) {
            mx = max(mx, last[i]);
            if (mx <= i) {
                return -1;
            }
            if (pre == i) {
                ++ans;
                pre = mx;
            }
        }
        return ans;
    }
};

Go:

func videoStitching(clips [][]int, time int) int {
	last := make([]int, time)
	for _, v := range clips {
		a, b := v[0], v[1]
		if a < time {
			last[a] = max(last[a], b)
		}
	}
	ans, mx, pre := 0, 0, 0
	for i, v := range last {
		mx = max(mx, v)
		if mx <= i {
			return -1
		}
		if pre == i {
			ans++
			pre = mx
		}
	}
	return ans
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

These code examples provide efficient solutions to the video stitching problem using a greedy approach. The time and space complexity analysis ensures that the solutions are optimized for performance.