Video Stitching

Problem

Given clips as [start, end] and a target time, return the minimum number of clips needed to cover the whole interval from 0 to time, or -1 if that is impossible.

Sort clips by start, then repeatedly extend the covered end as far as possible using all clips that start at or before it. If no remaining clip extends the coverage, return -1.

Hint

Each round consumes every clip starting at or before the current covered end.

Test cases

case 1

in: [[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]],10]

expected: 3

case 2

in: [[[0,1],[1,2]],5]

expected: -1

case 3

in: [[[0,1]],1]

expected: 1

case 4

in: [[[0,2]],1]

expected: 1

case 5

in: [[],5]

expected: -1

Starter codePython

def video_stitching(clips, time):
    # Your code here
    pass

5 test cases · run your code against them in the editor