1024. Video Stitching - cocoder39/coco39_LC GitHub Wiki

1024. Video Stitching

pretty much 45. Jump Game II

Option 1: Greedy T = O(n)

template

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        clips.sort()
        
        curEnd, nextEnd = 0, 0
        cnt = 0
        for left, right in clips:
            if left >= time:
                break
            
            if nextEnd < left:
                return -1
            
            if curEnd < left:
                curEnd = nextEnd
                cnt += 1
            nextEnd = max(nextEnd, right)
        
        if nextEnd < time:
            return -1
        
        if curEnd >= time:
            return cnt
        else:
            return cnt + 1

Option 2: greedy O(n)

converting to jump game II. 但是nextIdx 显得过于刻意并不直观

why for i in range(T): instead of for i in range(T+1): at the point i == T-1, there are 3 cases:

• curMaxPos < T-1: return -1
• curMaxPos == T-1: return count+1
• curMaxPos > T-1: return count

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        nextIdx = [0] * T
        for left, right in clips:
            if left < T:
                nextIdx[left] = max(nextIdx[left], right)
        
        count = 0
        curMaxPos = nextMaxPos = 0
        for i in range(T):
            nextMaxPos = max(nextMaxPos, nextIdx[i])
            if curMaxPos < i:
                return -1
            elif curMaxPos == i:
                count += 1
                curMaxPos = nextMaxPos
        return count

Option 3: T = O(n * range)

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort()
        dp = [0] + [T+1] * T
        for left, right in clips:
            for i in range(left+1, min(right, T) + 1):
                dp[i] = min(dp[i], dp[left]+1)
        return dp[-1] if (dp[-1] < T+1) else -1