Problem 1024

Abstract / Summary

Given video clips and a target time range, determine the minimum number of clips needed to cover the entire range without gaps.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1024.py

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        impossible = 9999

        clips.sort()

        @cache
        def deeper(pos):
            if pos >= time:     # done
                return 0

            best = impossible
            for start, end in clips:
                if start > pos: # gap
                    break

                if end   > pos: # stitch
                    best = min(best, 1 + deeper(end))

            return best

        return -1 if deeper(0) == impossible else deeper(0)
22 lines | 577 bytes | submitted March 17, 2024 | GitHub   18% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 52% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Dynamic Programming
  • Greedy
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the classic interval-cover problem: given a collection of video clips, each defined by a start and end time, determine the minimum number of clips required to cover a target interval [0, time]. The algorithm relies on sorting the input, a depth-first search with memoization, and early termination when a gap is detected.

Key Steps

Sorting the clips

clips.sort()

Sorting arranges the intervals in non-decreasing order of their start times (and, implicitly, end times for equal starts). This ordering enables the subsequent loop to stop as soon as a clip starts after the current position, guaranteeing that no later clip can fill the current gap.

Recursive search with caching

@cache
def deeper(pos):
    if pos >= time:     # done
        return 0

    best = impossible
    for start, end in clips:
        if start > pos: # gap
            break

        if end   > pos: # stitch
            best = min(best, 1 + deeper(end))

    return best

The inner function deeper receives the current coverage position pos. The base case returns 0 when the target time has been reached or exceeded, indicating that no further clips are needed.

A sentinel value impossible (set to a large constant) represents an unattainable solution. The loop iterates over the sorted clips. When a clip’s start exceeds pos, the loop breaks because the sorted order guarantees that all subsequent clips also start later, leaving an unavoidable gap. If a clip extends beyond pos, the algorithm recursively explores the state after using that clip, adding one to the count. The minimum of all feasible continuations is stored in best.

Final result handling

return -1 if deeper(0) == impossible else deeper(0)

The initial call starts from position 0. If the recursive search returns the sentinel value, the function reports -1 to indicate that covering the interval is impossible; otherwise, it returns the computed minimum number of clips.

Edge Cases Handled

When the target time is 0, the base case pos >= time is satisfied immediately, and the function returns 0, correctly indicating that no clips are needed.

If the input list clips is empty, the loop body never executes, best remains the sentinel, and the final return yields -1, reflecting the impossibility of coverage.

Clips that start before the current position but end at or before pos are ignored because the condition end > pos filters them out, preventing unnecessary recursive calls.

When multiple clips share the same start time, the sorted order preserves their relative end times, and the loop still evaluates each candidate, ensuring that the optimal longer extension is considered.

Gaps in coverage are detected by the if start > pos: break statement; as soon as a clip begins after the current position, the algorithm knows that no earlier clip can fill the gap, and it stops exploring that branch.

Performance Optimizations

The initial sorting step reduces the search space by allowing an early break on gaps, eliminating the need to scan the entire list for each recursive call.

Memoization via @cache stores the result of deeper(pos) for every distinct position encountered. This prevents repeated exploration of identical sub-problems, turning an exponential search into a tractable one.

Using a single large sentinel value (impossible = 9999) avoids the overhead of constructing special objects or raising exceptions for impossible paths, enabling fast integer comparisons.

The condition if end > pos ensures that only clips that actually extend coverage are considered, pruning branches that would not make progress.

Overall, the combination of sorted input, early termination on gaps, and cached recursion yields an efficient solution that scales well with the number of clips.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long, long movie tape that is exactly as long as the time number. You want to cover the whole tape using smaller pieces of tape from the list of clips. Think of this like building a bridge across a river using floating logs.

First, the computer puts all the little tape pieces in order from the smallest number to the biggest number so they are easy to look through. Then, a helper function starts at the very beginning of the tape. It looks at all the pieces that can reach the current spot. When it finds a piece that can start where the current tape ends, it picks that piece up and adds it to the collection.

The computer keeps doing this over and over, trying to find the fewest pieces possible to reach the end of the long tape. If it finds a gap where no piece can reach, it knows that path will not work. If it reaches the end of the tape, it remembers how many pieces it used. It keeps trying different combinations until it finds the smallest number of pieces that can finish the job from start to finish. If the computer tries every way possible and still cannot cover the whole tape, it finishes by saying it is not possible to do.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 6.41 | σ = 1.55

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
everthis JS
fsq C++
haoel C++
JoshCrozier JS
lkwq007 Python
suxrobGM C#
trung-hn Python
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fsq C++
haoel C++
JoshCrozier JavaScript
lkwq007 Python
suxrobGM C#
trung-hn Python
wisdompeak C++
28 links | 16 authors | 7 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality