class Solution:
def helper(self,l,r,clips)->int:
maxL,maxR=0,0
iL,iR=-1,-1
for i,c in enumerate(clips):
if c[0]<=l and c[1]>=r:
return 1
if c[0]<=l:
if c[1]-l>maxL:
maxL=c[1]-l
iL=i
if c[1]>=r:
print(r,c[0],c[1],maxR)
if r-c[0]>maxR:
maxR=r-c[0]
iR=i
if iL==-1 or iR==-1:
return -1
new_l=clips[iL][1]
new_r=clips[iR][0]
if clips[iL][0]==clips[iR][0] and clips[iL][1]==clips[iR][1]:
return 1
if new_l>=new_r:
return 2
clips=[c for i,c in enumerate(clips) if i not in (iL,iR)]
return 2+self.helper(new_l,new_r,clips)
def videoStitching(self, clips: List[List[int]], T: int) -> int:
return self.helper(0,T,clips)
Leetcode 1024. Video Stitching
点赞
收藏