1
# Runtime: 46 ms (Top 41.2%) | Memory: 16.25 MB (Top 82.7%)
2

3

4
class Solution:
5
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
6
        dp = [float("inf")] * (T + 1)
7
        dp[0] = 0
8
        for i in range(1, T + 1):
9
            for start, end in clips:
10
                if start <= i <= end:
11
                    dp[i] = min(dp[start] + 1, dp[i])
12
        if dp[T] == float("inf"):
13
            return -1
14
        return dp[T]