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];
}
}