Video Stitching

给一个数组, 里面是intervals, 给一个T, 问最少多少个intervals可以组成个[0, T]. interval可以任意剪短. 这个题可以不sort 直接dp, 也可以sort了dp. 先sort下后, dp[i]就表示达到i的最少intervals的数量. 所以就有了dp[i] = Math.min(dp[i], dp[interval[start]]+1). 然后注意判断下是否有解.

class Solution {
    public int videoStitching(int[][] clips, int T) {
        int res = 0;
        int[] dp = new int[200];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        Arrays.sort(clips, (a,b) ->  a[0] - b[0]);
        for(int[] c : clips) {
            for(int i = c[0]; i <= c[1]; i++) { 
                dp[i] = Math.min(dp[i], dp[c[0]] + 1);
            }
        }
        if(dp[T] >= Integer.MAX_VALUE / 2)
            return -1;
        else
            return dp[T];
    }
}