Java-LeetCode1024. 视频拼接-滑动窗口 | 动态规划

• 算法
  • 1.按照每组的左区间排序
  • 2.遍历每组区间，找到以当前start开始最多能到达的end，
    • 2.1 当start=end时，片段无法继续往后拼接返回-1
    • 2.2 否则，这样就是一个片段，然后把end赋给start接着遍历下一个窗口

public int videoStitching(int[][] clips, int T) {
    Arrays.sort(clips, (a, b) -> a[0] - b[0]);
    int result = 0;
    for (int start = 0, end = 0, i = 0; start < T; start = end) {
        for (; i < clips.length && clips[i][0] <= start; i++) {
            end = Math.max(end, clips[i][1]);
        }
        if (start == end) {
            return -1;
        }
        result++;
    }
    return result;
}

• 算法
  • 1.动态规划，dp[i]表示[0-i]至少需要多少个片段剪辑得来
  • 2.初始状态，dp[0] = 0；dp[i] = T + 1，i != 0
  • 3.过渡公式，dp[i] = Math.min(dp[i], dp[clip[0]] + 1) for clip in clips

public int videoStitching(int[][] clips, int T) {
    int[] dp = new int[T+1];
    Arrays.fill(dp, T+1);
    dp[0] = 0;
    for (int i = 1; i <= T && dp[i-1] < T; i++) {
        for (int[] clip : clips) {
            if (clip[0] <= i && i <= clip[1]) {
                dp[i] = Math.min(dp[i], dp[clip[0]]+1);
            }
        }
    }
    return dp[T] == T + 1 ? -1 : dp[T];
}