What is the brute force approach and complexity for Video Stitching?

Try taking or skipping every clip; keep the smallest set that covers [0, time] with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Video Stitching?

Sort by start; among clips starting inside the covered part, take the one reaching farthest with optimal time complexity O(N log N) and space complexity O(1).

How do you identify the pattern for Video Stitching?

Look for key signals in the prompt: "cover the whole range [0, time]" indicates Coverage: grow a covered stretch from the left with no gaps.; "minimum number of clips" indicates Fewest jumps — each clip pushes the covered edge forward.; "return −1 if impossible" indicates Detect a gap: the best reach doesn't move past the covered edge..

Video Stitching

Medium·LeetCode #1024 Pro OnlyMedium

LeetCode

Problem Statement

A sports event lasted time seconds. You have short video clips of it, each given as [start, end]: the clip shows the event from second start to second end. Clips can overlap and can have any length.

You may cut clips into smaller pieces freely. Pick the fewest clips whose pieces together show the whole event [0, time], with no missing moment. If it can't be done, return -1.

Input

An array clips where clips[i] = [start_i, end_i], and an integer time.

Output

One integer: the minimum number of clips, or -1.

Example 1

Input: clips = [[0,2], [4,6], [8,10], [1,9], [1,5], [5,9]], time = 10

Output: 3

Use [0,2], [1,9] and [8,10]. Together they cover 0 to 10.

Example 2

Input: clips = [[0,1], [1,2]], time = 5

Output: -1

Nothing covers anything after second 2.

Example 3

Input: clips = [[0,1], [6,8], [0,2], [5,6], [0,4], [0,3], [6,7], [1,3], [4,7], [1,4], [2,5], [2,6], [3,4], [4,5], [5,7], [6,9]], time = 9

Output: 3

Use [0,4], [4,7] and [6,9].

Constraints

• 1 ≤ clips.length ≤ 100
• 0 ≤ start_i ≤ end_i ≤ 100
• 1 ≤ time ≤ 100

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“cover the whole range [0, time]”

→ Coverage: grow a covered stretch from the left with no gaps.

“minimum number of clips”

→ Fewest jumps — each clip pushes the covered edge forward.

“return −1 if impossible”

→ Detect a gap: the best reach doesn't move past the covered edge.

Approach Complexity Ladder

Brute Force — try every subset of clipsO(2^N)O(N)

Try taking or skipping every clip; keep the smallest set that covers [0, time]

Better — DP over secondsO(T · N)O(T)

dp[t] = fewest clips covering [0, t]; try every clip as the last piece

Optimal — greedy farthest reach (Jump Game II)O(N log N)O(1)

Sort by start; among clips starting inside the covered part, take the one reaching farthest

Brute Force Intuition

Sort by start. For each clip, try both: skip it, or take it. A clip can only be taken if it starts inside what is already covered, because later clips start even later and could never fill the gap. Whenever the covered part reaches time, record how many clips were used.

Recognition rule for this sub-pattern:

Pick or remove intervals to optimise coverage. Sorting by end and keeping the earliest finisher leaves the most room.

Remember this · Intervals

Trigger

Input is [start, end] pairs; overlap, merge, insert, meeting rooms, free time, minimum removals.

Think

After sorting, do I only ever need to compare against the most recent interval?

Key question

Sort by start or by end — which one makes the greedy choice obvious?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture