This is a greedy on intervals, which is a sort of optimized BFS.
This is like jump game. You can see jump game as bfs because you can look at the farthest reachable places as demarcating the ends of levels.
class Solution:
def videoStitching(self, clips: List[List[int]], time: int) -> int:
# Sort by start time.
# End tie-breaking doesn't matter if we take max end during the scan
clips.sort()
count = 0
current_end = 0
farthest_reach = 0
i = 0
n = len(clips)
# We continue as long as we haven't covered the whole time
while current_end < time:
# Process all clips that start before or when the current clip ends
while i < n and clips[i][0] <= current_end:
farthest_reach = max(farthest_reach, clips[i][1])
i += 1
# If we couldn't find a clip to extend our range, we're stuck!
if farthest_reach == current_end:
return -1
# Let's extend to the farthest possible point!
current_end = farthest_reach
count += 1
return count