You are given a series of video clips from a sporting event that lasted T seconds.  These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1].  We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]).  If the task is impossible, return -1.
 
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation: 
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation: 
We can't cover [0,5] with only [0,1] and [1,2].

Example 3:
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation: 
We can take clips [0,4], [4,7], and [6,9].

Example 4:
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation: 
Notice you can have extra video after the event ends.

 
Constraints:

1 <= clips.length <= 100
0 <= clips[i][0] <= clips[i][1] <= 100
0 <= T <= 100

Difficulty: interview

Starter code:

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        

Solutions:
class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort(key=lambda x: [x[0], -x[1]])
        res = 0            
        r = 0
        new_r = 0
        # print(clips)
        for s, e in clips:
            if s <= r:
                new_r = max(new_r, e)
            elif s > new_r:
                return -1
            else:
                res += 1
                r = new_r
                # print(new_r)
                new_r = max(new_r, e)
            if new_r >= T:
                break
        if new_r < T:
            return -1
        if r < T and new_r >= T:
            res += 1
        return res


class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        # First find clips that start from 0
            # Then use the clip that reaches the farthest
        # Continually find clips that continue, and pick ones that reach the farthest
        
        last_end = 0
        clip_count = 0
        while last_end < T:
            # If no more clips
            if clip_count >= len(clips):
                return -1
            # Find valid clip that reaches the farthest
            max_end = -1
            for clip in clips:
                if clip[0] <= last_end:
                    if clip[1] > max_end:
                        max_end = clip[1]
            
            if max_end >= 0:
                last_end = max_end
                clip_count += 1
            else:
                return -1
            
        return clip_count


class Solution:
    
    def videoStitching(self, clips, T):
        end, end2, res = -1, 0, 0
        for i, j in sorted(clips):
            if end2 >= T or i > end2:
                break
            elif end < i <= end2:
                res, end = res + 1, end2
            end2 = max(end2, j)
        return res if end2 >= T else -1    

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        
        dp = [T+1] * (T+1)
        dp[0] = 0
        i = 1
        while i <= T and dp[i-1] < T:
            for c in clips:
                if c[0] <= i and i <= c[1]:
                    dp[i] = min(dp[i], dp[c[0]] + 1)
            i+=1
        return dp[T] if dp[T] != T+1 else -1

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort(key=lambda x:x[0])
        n = len(clips)
        memo = {}
        def recur(i,interval):
            if (i,interval) in memo:
                return memo[(i,interval)]
            if interval >= T:
                return 0
            if i==n:
                return sys.maxsize 
            if interval >= clips[i][0] and interval < clips[i][1]:
                ans = min(recur(i+1,clips[i][1])+1,recur(i+1,interval))
            else:
                ans = recur(i+1,interval)
            memo[(i,interval)] = ans
            return ans
        fnl = recur(0,0)
        return -1 if fnl == sys.maxsize else fnl
        
            
            


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

class Solution:
    import json
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        IMPOSSIBLE = float('inf')
        sorted_clips = sorted(clips, key=lambda x: x[0], reverse=False)
        opt = {}
        for index, clip in enumerate(sorted_clips):
            for t in range(0, T+1):
                start, end = tuple(clip)
                if t == 0:
                    opt[index, t] = 0
                elif index == 0:
                    opt[index, t] = 1 if start == 0 and t <= end else IMPOSSIBLE
                else:
                    opt[index, t] = min(opt[index-1, t], opt[index-1, min(start, t)]+1 if t <= end else IMPOSSIBLE)
        print(opt)
        return opt[len(clips)-1, T] if opt[len(clips)-1, T] != float('inf') else -1

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort()
        n = len(clips)
        dp = [float('inf')]*(T+1)
        dp[0] = 0
        for i in range(1, T+1):
            for j in range(n):
                if clips[j][0]<=i<=clips[j][1]:
                    dp[i] = min(dp[i], 1+dp[clips[j][0]])
        if dp[T] == float('inf'):
            return -1
        return dp[-1]


class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort()
        i = 0
        end = 0
        res = 0
        
        while end < T:
            current_end = 0
            while i < len(clips) and clips[i][0] <= end: # basically stating while there is an overlap, keep doing this loop
                current_end = max(current_end, clips[i][1]) # trying to extend end time as far as possible 
                i += 1
            if current_end <= end:
                return -1
            end = current_end
            res += 1
        return res # if the new end is not greater than or equal then it means there are no intervals in which you can extend to the end of the clip

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        end, end2, cnt= -1, 0, 0 # end 表示上一段最后截止点，end2表示当前可以最大延伸的最远地点
        for s, e in sorted(clips):
            if end2>=T or s> end2: # end2>=T表示已经找到一个可以cover所有T； s>end2表示完全接不上（因为已经排过序了）
                break
            elif end< s <= end2: # 如果s=end 说明新的这段和上一段有overlap，只需要看新的这段是不是比上一段cover更多 来跟新end2
                cnt+=1
                end = end2
            end2= max(end2, e)
        return cnt if end2>=T else -1

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        step = 0 
        l, r = -1, 0
        for i,j in sorted(clips):
            if r >= T:
                return step
            if i>r:
                return -1
            
            if l<i<=r:
                step += 1
                l = r          
            r = max(r, j)            
        return step if r>=T else -1

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        dp = [float(inf)] * (101)
        clips.sort()
        if clips[0][0] > 0:
            return -1
        dp[0] = 0
        for i in range(len(clips)):
            clip = clips[i]

            if clip[0] != 0 and dp[clip[0]] == float(inf):
                break
            
            # if clip[0] == 0:
            #     min_so_far = 0
            # else:
            min_so_far = dp[clip[0]]
            
            for k in range(clip[0], clip[1] + 1):
                dp[k] = min(dp[k], min_so_far + 1)
        
        if dp[T] == inf:
            return -1
        return dp[T]

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        dp = [float(inf)] * (101)
        clips.sort()
        if clips[0][0] > 0:
            return -1

        for i in range(len(clips)):
            clip = clips[i]

            if clip[0] != 0 and dp[clip[0]] == float(inf):
                break
            
            if clip[0] == 0:
                min_so_far = 0
            else:
                min_so_far = dp[clip[0]]
            
            for k in range(clip[0], clip[1] + 1):
                dp[k] = min(dp[k], min_so_far + 1)
        
        if dp[T] == inf:
            return -1
        return dp[T]

import math

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort()
        longest = sorted(clips, key=lambda a: a[1])[-1][1]
        memo = [[None for i in range(longest + 1)] for i in range(len(clips))]
        
        def dp(i, start):
            if start >= T:
                return 0
            
            curr = clips[i]
            if curr[0] > start:
                return math.inf
            elif i == len(clips) - 1:
                if curr[1] < T:
                    return math.inf
                return 1
            
            # Pick first clip
            if memo[i + 1][curr[1]] == None:
                memo[i + 1][curr[1]] = dp(i + 1, curr[1])
            
            #Don't pick first clip
            if memo[i + 1][start] == None:
                memo[i + 1][start] = dp(i + 1, start)
            
            return min(1 + memo[i + 1][curr[1]], memo[i + 1][start])
        
        res = dp(0, 0)
        return res if res != math.inf else -1

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        table = [101] * 101
        table[0] = 0
        
        changed = True
        while changed:
            changed = False
            for i, j in clips:
                for k in range(i, j+1):
                    if table[i] + 1 < table[k]:
                        table[k] = table[i] + 1
                        changed = True
        
        if table[T] < 101:
            return table[T]
        else:
            return -1

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        clips.sort(key=lambda x: x[0])
        dp = [[0]*(len(clips)+1)]+[[float('inf')]*(len(clips)+1) for _ in range(T)]
        for row in range(1, len(dp)):
            for col in range(1, len(dp[0])):
                dp[row][col] = dp[row][col-1]
                if(clips[col-1][0] <= row-1 < clips[col-1][1]):
                    dp[row][col] = min(dp[row][col], 1+dp[clips[col-1][0]][col])
        ans = dp[-1][-1] if dp[-1][-1]!=float('inf') else -1
        return ans