1024. 视频拼接

解法一：动态规划

先按起始位置升序排列，状态初始化后遍历视频片段进行状态转移。

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    private final static int MAX = 1000;
    public int videoStitching(int[][] clips, int T) {
        // dp[i]表示拼接出[0, i]这个片段所需要的最小视频数
        int[] dp = new int[101];
        // 先按起始位置升序排列
        Arrays.fill(dp, MAX);
        Arrays.sort(clips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        if (clips[0][0] > 0) {
            return -1;
        }
        // 状态初始化
        int i = 0;
        while (clips[i][0] == 0) {
            for (int j = clips[i][0]; j <= clips[i][1]; ++j) {
                dp[j] = 1;
            }
            ++i;
        }
        // 状态转移
        for (; i < clips.length; ++i) {
            for (int j = clips[i][0]; j <= clips[i][1]; ++j) {
                dp[j] = Math.min(dp[j], dp[clips[i][0]] + 1);
            }
        }
        // 根据是否有解输出答案
        if (dp[T] != MAX) {
            return dp[T];
        } else {
            return -1;
        }
    }
}