- This problem can be solved by a greedy algorithm.
-
res represents the number of steps; current represents the farthest time we could reach with res steps. In the while loop, go through all the clips and find all the clips which cross the time current, because these clips can be used to extend current.
- If
current reaches T, return the number of steps res. If such clips do not exist, then current cannot be extended any more, and we should return -1.
class Solution:
def videoStitching(self, clips: List[List[int]], T: int) -> int:
res, current = 0, 0
while True:
current = max([j for i, j in clips if i <= current and j > current], default=0)
if current == 0: return -1
if current >= T: return res + 1
res += 1
