Video Stitching

Video Stitching

What is this problem about?

The "Video Stitching" interview question asks you to find the minimum number of video clips needed to cover a specific time interval [0, T]. You are given a set of clips, each with a start and end time. If you cannot cover the entire interval, you return -1.

Why is this asked in interviews?

Companies like Google use the "Video Stitching" coding problem to test a candidate's ability to implement a "Greedy interview pattern." It is very similar to the "Jump Game II" problem and requires you to make locally optimal choices to find a globally optimal solution. It assesses your ability to handle interval-based logic.

Algorithmic pattern used

The "Greedy" approach is the most efficient. You sort the clips by start time. At each step, you look at all clips that start before or at the current "reached" time and pick the one that extends the "furthest." You repeat this until you reach T or find that no more clips can extend the current interval.

Example explanation

Interval: [0, 10], Clips: [[0, 2], [1, 5], [1, 9], [4, 6], [8, 10]]

1. Start at 0. Possible clips: [0, 2]. New reach = 2. Clips used = 1.
2. At reach 2. Possible clips starting <= 2: [1, 5], [1, 9].
3. Pick [1, 9] because it extends the furthest. New reach = 9. Clips used = 2.
4. At reach 9. Possible clips starting <= 9: [4, 6], [8, 10].
5. Pick [8, 10]. New reach = 10. Clips used = 3.
6. Result: 3.

Common mistakes candidates make

A common mistake is trying to use Dynamic Programming, which works but is O(T * n) or O(n²), whereas the Greedy approach is O(n log n) due to sorting. Another error is not correctly handling cases where there is a "gap" in the clips (e.g., clips are [0, 2] and [3, 5]), making it impossible to cover [0, 5].

Interview preparation tip

When solving the "Video Stitching" coding problem, think of it as "how far can I go with one more clip?" This mindset is key to solving many greedy interval problems. Always clarify if clips can be used partially (in this problem, they can).