Video Stitching

AeroSpace • Anduril • Medium • greedy interval cover

A surveillance drone records footage in clips [start, end] (seconds). Stitch the minimum number of clips to cover the timeline [0, T]. Clips may overlap; you may re-use the same clip only once. Return −1 if coverage is impossible.

Example: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 → 3 (greedy jumps: 0→9→10 using three stitch steps).
Demo uses this example on a horizontal timeline.

TimeO(n log n)

SpaceO(1)

Ans—

Clip segment

Active / scanning

cur pointer

far reach

Covered [0, cur]

step—

clip i—

coverage—

Variable watch

Press Step or Play.

clips (sorted)

—

Speed:

Ready

Greedy: sort clips, then extend far with every clip whose start ≤ cur; jump cur = far and increment count.

Type It

video_stitching(clips, T) — minimum clips to cover [0, T]. Sort by start; greedy far extension then jump.

═══ VIDEO STITCHING ═══

① clips.sort() by start

② while cur < T: scan clips[i] with start ≤ cur → far = max(far, end)

if far == cur → return -1

③ count += 1; cur = far

④ return count