duration seconds and several camera operators filmed it. Each recording is a pair [start, end] in the array clips: it covers the match from second start to second end. Recordings may overlap and vary in length.
You may cut any piece out of a recording, so overlaps are not a problem. You want to assemble the complete broadcast, the interval [0, duration], using as few recordings as possible.
Return the minimum number of recordings needed, or -1 if some part of the match was not filmed by anyone.clips=[[0, 3], [2, 6], [5, 8], [1, 7]], duration=8 → 3
No clip starting at 0 reaches past second 3, and no clip starting by second 3 reaches past 7, so a third clip is needed: for example [0, 3], [1, 7], [5, 8].
clips=[[0, 2], [3, 5]], duration=5 → -1
Nothing was filmed between seconds 2 and 3, so the answer is -1.
clips=[[0, 4], [0, 9], [4, 9]], duration=9 → 1
clips=[[0, 3], [2, 6], [5, 8], [1, 7]], duration=8
3
Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.