动态规划 区间调度问题 之 最长区间调度

该问题大致为, 给定 n 个工作的开始时间 与 结束时间,要求选择其中若干份工作参与, 参与一份工作 至始至终都全程参与,包括端点。而且 任意两份工作的  工作时间不能有交叉。  问  最后能够工作的最长时间。

《动态规划 区间调度问题 之 最长区间调度》

 思路:代码和最多区间调度最大的不同在选择第i个区间时。在这里用了一个二分查找来搜索不重叠的位置,然后判断该位置是否存在。如果不重叠位置存在,则算出当前的最大区间长度和;如果不存在,表明第i个区间和前面的所有区间均重叠,但由于我们还要选择第i个区间,所以暂时的最大区间和也即第i个区间自身的长度。在最多区间调度中,如果该位置不存在,我们直接将dp[i]赋值成dp[i-1],在这里我们却要将第i个区间本身的长度作为结果。从图五我们可以清楚地看到解释,在计算左下角的区间时,它和前面的两个区间都重合,但是它却包含在最优解中,因为它的长度比前面两个的和还要长。

 

例题:

看直播

Description

小明喜欢看直播,他订阅了很多主播,主播们有固定的直播时间 [Li, Ri] 。可是他网速只有2M,不能同时播放两个直播,所以同一时间只能看一个直播。并且他只会去看能完整看完的直播(从开播到停播都能观看)。他想知道最多能看多长时间的直播呢?注意 [1, 3] 和 [3, 4] 不能两者都选择。

Input

第一行一个N。

接下来N行每行两个整数Li, Ri。

1 <= N <= 2e5

1 <= Li <= Ri <= 1e9

Output

输出最多能看的时间。

Sample Input 1 

3
1 3
2 6
5 8

Sample Output 1 

7

具体看代码:

#include<bits/stdc++.h>
#define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl
#define pii pair<int,int>
#define clr(a,b) memset((a),b,sizeof(a))
#define rep(i,a,b) for(int i = a;i < b;i ++)
#define pb push_back
#define MP make_pair
#define LL long long
#define ull unsigned LL
#define ls i << 1
#define rs (i << 1) + 1
#define fi first
#define se second
#define ptch putchar
#define CLR(a) while(!(a).empty()) a.pop()

using namespace std;
inline LL read() {
    LL s = 0,w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(isdigit(ch))
        s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
inline void write(LL x) {
    if(x < 0)
        putchar('-'), x = -x;
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int maxn = 2e5 + 10;
pii p[maxn];
LL dp[maxn];
int n;

bool cmp(pii A,pii B){
    if(A.se != B.se) return A.se < B.se;
    return A.fi < B.fi;
}

int Search(int st){
    int l = 0,r = n;
    int ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(p[mid].se < st){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return ans;
}

int main() {
    n = read();
    rep(i,1,n + 1){
        p[i].fi = read();
        p[i].se = read();
    }
    sort(p + 1,p + 1 + n,cmp);
    for(int i = 1;i <= n;++ i){
        int index = Search(p[i].fi);
        LL tmp = (index > 0 ? dp[index] : 0) + p[i].se - p[i].fi + 1;
        dp[i] = max(dp[i - 1],tmp);
    }
    write(dp[n]);
    return 0;
}

 

    原文作者:Error Man
    原文地址: https://blog.csdn.net/no_O_ac/article/details/82559178
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞