这题有点贪心的思想,将有交集的区间合并,然后求最长连续时间和最长不连续时间就可以了。。

我们先将区间按照起始时间从小到大的时间排序,假设(a,b)和(c,d),如果c在(a,b)内,则区间长度可以更新为(a,max(b,d)).如果不在(a,b)区间,

则c-b为不连续时间,并一直往下更新。。

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7f7f7f7f;
struct T
{
    int sat,ed;
}p[5010];
bool cmp(T a,T b)
{
    if(a.sat!=b.sat)
        return a.sat<b.sat;
    return a.ed<b.ed;
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d%d",&p[i].sat,&p[i].ed);
    sort(p,p+n,cmp);
    int sat=p[0].sat,ed=p[0].ed;
    int preed=0;
    int maxxa=ed-sat,maxxb=0;
    for(i=1;i<n;i++)
    {
        if(p[i].sat>=sat&&p[i].sat<=ed)
        {
            if(p[i].ed>ed)
                ed=p[i].ed;
        }
        else
        {
            preed=ed;
            maxxa=max(maxxa,ed-sat);
            sat=p[i].sat;
            ed=p[i].ed;
            maxxb=max(maxxb,sat-preed);
        }
    }
    printf("%d %d\n",maxxa,maxxb);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation