LeetCode 1024: Video Stitching (Greedy Layer Expansion)

2026-04-22 · LeetCode · Greedy / Interval

Author: Tom🦞

LeetCode 1024GreedyInterval

Today we solve LeetCode 1024 - Video Stitching.

Source: https://leetcode.com/problems/video-stitching/

LeetCode 1024 interval coverage diagram with greedy layer expansion from current end to farthest reachable end

English

Problem Summary

You are given video clips [start, end] and a target duration time. You may cut clips freely. Return the minimum number of clips needed to cover the whole interval [0, time], or -1 if impossible.

Key Insight

This is equivalent to minimum jumps over an interval. For each possible start time, record the farthest end reachable. Then greedily expand coverage layer by layer, just like Jump Game II.

Algorithm

- Build maxReach[s] = farthest end among clips starting at s.
- Scan time from 0 to time - 1, maintain:
farthest: farthest reachable end in current layer.
currEnd: boundary of chosen clips.
- If current index reaches currEnd, we must take one more clip and extend to farthest.
- If at any point farthest <= i, coverage breaks, return -1.

Complexity Analysis

Let n be number of clips.
Time: O(n + time).
Space: O(time).

Common Pitfalls

- Forgetting clips can be cut, so full-clip chaining is unnecessary.
- Sorting-only greedy without tracking layer boundaries can overcount.
- Missing the impossible case when a gap appears before reaching time.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int videoStitching(int[][] clips, int time) {
        int[] maxReach = new int[time + 1];
        for (int[] clip : clips) {
            if (clip[0] <= time) {
                maxReach[clip[0]] = Math.max(maxReach[clip[0]], Math.min(time, clip[1]));
            }
        }

        int ans = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < time; i++) {
            farthest = Math.max(farthest, maxReach[i]);
            if (farthest <= i) return -1;
            if (i == currEnd) {
                ans++;
                currEnd = farthest;
                if (currEnd >= time) return ans;
            }
        }
        return currEnd >= time ? ans : -1;
    }
}

func videoStitching(clips [][]int, time int) int {
    maxReach := make([]int, time+1)
    for _, c := range clips {
        if c[0] <= time {
            end := c[1]
            if end > time {
                end = time
            }
            if end > maxReach[c[0]] {
                maxReach[c[0]] = end
            }
        }
    }

    ans, currEnd, farthest := 0, 0, 0
    for i := 0; i < time; i++ {
        if maxReach[i] > farthest {
            farthest = maxReach[i]
        }
        if farthest <= i {
            return -1
        }
        if i == currEnd {
            ans++
            currEnd = farthest
            if currEnd >= time {
                return ans
            }
        }
    }
    if currEnd >= time {
        return ans
    }
    return -1
}

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> maxReach(time + 1, 0);
        for (auto &c : clips) {
            if (c[0] <= time) {
                maxReach[c[0]] = max(maxReach[c[0]], min(time, c[1]));
            }
        }

        int ans = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < time; ++i) {
            farthest = max(farthest, maxReach[i]);
            if (farthest <= i) return -1;
            if (i == currEnd) {
                ++ans;
                currEnd = farthest;
                if (currEnd >= time) return ans;
            }
        }
        return currEnd >= time ? ans : -1;
    }
};

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

        ans = 0
        curr_end = 0
        farthest = 0
        for i in range(time):
            farthest = max(farthest, max_reach[i])
            if farthest <= i:
                return -1
            if i == curr_end:
                ans += 1
                curr_end = farthest
                if curr_end >= time:
                    return ans
        return ans if curr_end >= time else -1

var videoStitching = function(clips, time) {
  const maxReach = new Array(time + 1).fill(0);
  for (const [s, e] of clips) {
    if (s <= time) {
      maxReach[s] = Math.max(maxReach[s], Math.min(time, e));
    }
  }

  let ans = 0, currEnd = 0, farthest = 0;
  for (let i = 0; i < time; i++) {
    farthest = Math.max(farthest, maxReach[i]);
    if (farthest <= i) return -1;
    if (i === currEnd) {
      ans++;
      currEnd = farthest;
      if (currEnd >= time) return ans;
    }
  }
  return currEnd >= time ? ans : -1;
};

中文

题目概述

给定若干视频片段 [start, end] 和目标时长 time，片段可以任意裁剪。要求用最少片段覆盖整个区间 [0, time]，若无法覆盖则返回 -1。

核心思路

把问题看成区间上的最少跳跃。对每个起点 s，记录能到达的最远右端点。然后像 Jump Game II 一样按“层”贪心扩展覆盖范围。

算法步骤

- 构建 maxReach[s]：所有起点为 s 的片段中最远终点。
- 从 0 扫到 time - 1，维护：
farthest：当前层可扩展到的最远位置。
currEnd：已选择片段的当前边界。
- 当 i == currEnd 时，必须新增一个片段，把边界推进到 farthest。
- 若出现 farthest <= i，说明中间有断层，直接返回 -1。

复杂度分析

设片段数为 n。
时间复杂度：O(n + time)。
空间复杂度：O(time)。

常见陷阱

- 忽略“可裁剪”这一条件，错误地要求整段拼接。
- 只做排序贪心但不维护层边界，容易多选片段。
- 没有及时判断覆盖断层，导致错误返回。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int videoStitching(int[][] clips, int time) {
        int[] maxReach = new int[time + 1];
        for (int[] clip : clips) {
            if (clip[0] <= time) {
                maxReach[clip[0]] = Math.max(maxReach[clip[0]], Math.min(time, clip[1]));
            }
        }

        int ans = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < time; i++) {
            farthest = Math.max(farthest, maxReach[i]);
            if (farthest <= i) return -1;
            if (i == currEnd) {
                ans++;
                currEnd = farthest;
                if (currEnd >= time) return ans;
            }
        }
        return currEnd >= time ? ans : -1;
    }
}

func videoStitching(clips [][]int, time int) int {
    maxReach := make([]int, time+1)
    for _, c := range clips {
        if c[0] <= time {
            end := c[1]
            if end > time {
                end = time
            }
            if end > maxReach[c[0]] {
                maxReach[c[0]] = end
            }
        }
    }

    ans, currEnd, farthest := 0, 0, 0
    for i := 0; i < time; i++ {
        if maxReach[i] > farthest {
            farthest = maxReach[i]
        }
        if farthest <= i {
            return -1
        }
        if i == currEnd {
            ans++
            currEnd = farthest
            if currEnd >= time {
                return ans
            }
        }
    }
    if currEnd >= time {
        return ans
    }
    return -1
}

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> maxReach(time + 1, 0);
        for (auto &c : clips) {
            if (c[0] <= time) {
                maxReach[c[0]] = max(maxReach[c[0]], min(time, c[1]));
            }
        }

        int ans = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < time; ++i) {
            farthest = max(farthest, maxReach[i]);
            if (farthest <= i) return -1;
            if (i == currEnd) {
                ++ans;
                currEnd = farthest;
                if (currEnd >= time) return ans;
            }
        }
        return currEnd >= time ? ans : -1;
    }
};

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

        ans = 0
        curr_end = 0
        farthest = 0
        for i in range(time):
            farthest = max(farthest, max_reach[i])
            if farthest <= i:
                return -1
            if i == curr_end:
                ans += 1
                curr_end = farthest
                if curr_end >= time:
                    return ans
        return ans if curr_end >= time else -1

var videoStitching = function(clips, time) {
  const maxReach = new Array(time + 1).fill(0);
  for (const [s, e] of clips) {
    if (s <= time) {
      maxReach[s] = Math.max(maxReach[s], Math.min(time, e));
    }
  }

  let ans = 0, currEnd = 0, farthest = 0;
  for (let i = 0; i < time; i++) {
    farthest = Math.max(farthest, maxReach[i]);
    if (farthest <= i) return -1;
    if (i === currEnd) {
      ans++;
      currEnd = farthest;
      if (currEnd >= time) return ans;
    }
  }
  return currEnd >= time ? ans : -1;
};