# LeetCode 1024: Video Stitching

## Problem Restatement

We are given an array `clips` where `clips[i] = [start_i, end_i]` represents a video clip covering the time interval `[start_i, end_i]`.

We want to cover the interval `[0, time]` by choosing some of these clips.

We need to return the minimum number of clips needed, or `-1` if it is impossible.

Clips can be cut, so using only a portion of a clip is allowed.

The official constraints state that `1 <= clips.length <= 100`, `0 <= start_i <= end_i <= 100`, and `1 <= time <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `clips` and integer `time` |
| Output | Minimum number of clips to cover `[0, time]`, or `-1` |

Function shape:

```python
def videoStitching(clips: list[list[int]], time: int) -> int:
    ...
```

## Examples

Example 1:

```python
clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
time = 10
```

Choose clips `[0,2]`, `[1,9]`, `[8,10]`:

- `[0,2]` covers `[0,2]`
- `[1,9]` extends coverage to `[0,9]`
- `[8,10]` extends to `[0,10]`

Answer:

```python
3
```

Example 2:

```python
clips = [[0,1],[1,2]]
time = 5
```

These two clips only cover `[0,2]`, not `[0,5]`.

Answer:

```python
-1
```

## Key Insight

This is the classic greedy interval covering problem.

At each step, from the current coverage end, greedily pick the clip that extends coverage the furthest.

## Algorithm

1. Build a map `max_end[s]` = the furthest end reachable from start `s`.
2. Initialize `count = 0`, `current_end = 0`, `farthest = 0`.
3. For each time unit `t` from `0` to `time - 1`:
   - Update `farthest = max(farthest, max_end.get(t, 0))`.
   - If `t == current_end`:
     - If `farthest == current_end`, return `-1` (stuck).
     - Increment `count`.
     - `current_end = farthest`.
4. Return `count`.

## Correctness

At each step, we pick the clip that extends coverage the most. This greedy choice is optimal because choosing any clip with a shorter extension would only make future choices harder.

If at any position we cannot extend coverage, the task is impossible.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + time)` | Process clips once, then iterate over time |
| Space | `O(time)` | Map of max endpoints |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def videoStitching(self, clips: list[list[int]], time: int) -> int:
        max_end = [0] * (time + 1)
        for s, e in clips:
            if s <= time:
                max_end[s] = max(max_end[s], e)

        count = 0
        current_end = 0
        farthest = 0

        for t in range(time):
            farthest = max(farthest, max_end[t])
            if t == current_end:
                if farthest == current_end:
                    return -1
                count += 1
                current_end = farthest

        return count
```

## Code Explanation

Build the array of furthest reachable endpoints:

```python
max_end = [0] * (time + 1)
for s, e in clips:
    if s <= time:
        max_end[s] = max(max_end[s], e)
```

Greedy scan:

```python
for t in range(time):
    farthest = max(farthest, max_end[t])
    if t == current_end:
        if farthest == current_end:
            return -1
        count += 1
        current_end = farthest
```

When we reach `current_end`, we must pick the next clip. The best choice extends coverage to `farthest`.

If `farthest` has not advanced beyond `current_end`, it is impossible.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.videoStitching([[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], 10) == 3
    assert s.videoStitching([[0,1],[1,2]], 5) == -1
    assert s.videoStitching([[0,5]], 5) == 1
    assert s.videoStitching([[0,1],[0,2],[0,3]], 3) == 1
    assert s.videoStitching([[0,1],[1,2],[2,3]], 3) == 3

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `3` | Three clips cover `[0,10]` |
| Impossible | `-1` | Gap from `2` to `5` |
| Single clip | `1` | One clip covers the range |
| Overlapping start | `1` | Best clip covers entire range |
| Sequential clips | `3` | Each clip covers one unit |