LeetCode 题解
    1024. Video Stitching

    1024. Video Stitching

    给定一组片段的头和尾，求能拼成 0-T 分钟的最少选择片段个数

    DP 做法： 每一个 0-T 的每一个段都有一个选择个数，考虑每一个段与每一个给定片段的关系，可以分成五种情况

    // time: O(N³)
// space: O(N²)

int videoStitching(vector<vector<int>>& clips, int T) {
    int kInf=101;
    vector<vector<int> > dp(T+1, vector<int>(T+1, kInf));
    for(auto clip : clips) {
        int s=clip[0];
        int e=clip[1];

        for(int l=1;l<=T;++l) {
            for(int i=0;i<=T-l;++i) {
                int j=i+l;
                if (s > j || e < i) continue;
                if (s<=i && e>=j) dp[i][j]=1;
                else if (s <= i) dp[i][j]=min(dp[i][j], dp[e][j]+1);
                else if (e >= j) dp[i][j]=min(dp[i][j], dp[i][s]+1);
                else dp[i][j]=min(dp[i][j], dp[i][s]+dp[e][j]+1);
            }
        }
    }

    return dp[0][T] == kInf ? -1 : dp[0][T];
}

    贪心： 直接排序，然后每次都取满足起始点情况下最远的终点

    // time: O(NlogN)
// space: O(1)

int videoStitching(vector<vector<int>>& clips, int T) {
    sort(clips.begin(), clips.end());
    int res=0;
    for(int i=0,st=0,end=0;st<T;st=end, ++res) {
        while(i<clips.size() && clips[i][0]<=st)
            end=max(end, clips[i++][1]);
        if (end==st) return -1;
    }
    return res;
}

    #DP #greedy

    1018. Binary Prefix Divisible By 51025. Divisor Game