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). 然后注意判断下是否有解.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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]; } } |