题目大意:

给你 n 个区间(n<1e5),每个区间为 [ L , R ](0 <= L <= R <= 1e9)。另给你一个整数 m(0 <= m <= 1e9)。区间可能会有重合,你可以填补区间之间的空隙,最多可以填补 m 个格子。现在问你最长不间断区间有多长。

注:m个格子可以填充任意位置,包括所有区间中最右端点的右侧。但填充位置不能是0号格子左侧。

分析:

区间合并:

各区间按左端点的靠左顺序排序,之后遍历所有区间;如果当前区间的右端点在下一个区间的左端点右侧,那么如果下一个区间的右端点在当前区间右端点右侧,则更新当前区间右端点。如果下一个区间左端点在当前区间右端点右侧,则储存当前区间,并令下一区间作为新的当前区间。

尺取区间:

对于一个确定的左侧区间,不断添加右侧区间,直到区间间隙之和大于 m ,再删除左侧区间直至区间间隙之和小于 m ,再继续添加右侧区间。整个过程中时刻更新能取到的最长区间的值。

代码:

#include<bits/stdc++.h>
#define maxn 100050

using namespace std;

int m,n;
struct range
{
    int l;int r;
}a[maxn];

range b[maxn];
bool x_cmp(range c,range d)
{
    return c.l<d.l;
}
int gap[maxn];

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].l,&a[i].r);
        }
        sort(a,a+n,x_cmp);

//-----------------------------------------------------------------------------------
        int tl=a[0].l,tr=a[0].r;//当前左端点和右端点
        int num=0;
        for(int i=1;i<n;i++)
        {
            if(tr+1<a[i].l)
            {
                b[num].l=tl;
                b[num].r=tr;
                num++;
                tl=a[i].l;
                tr=a[i].r;
                continue;
            }
            if(tr<a[i].r)
            {
                tr=a[i].r;
            }
        }
        b[num].l=tl;b[num].r=tr;
//-------------------------------------------------------------------------------

        /*for(int i=0;i<=num;i++) { cout<<b[i].l<<","<<b[i].r<<endl; }*/
        int x_sum=0;
        int ans=m;
        tl=0;tr=0;
        int temp=0;
        while(tr<num)
        {
            tr++;
            x_sum+=(b[tr].l-b[tr-1].r-1);
            if(x_sum>m)
            {
                temp=(b[tr-1].r-b[tl].l+1)+(m-(x_sum-(b[tr].l-b[tr-1].r-1)));
                if(ans<temp)
                {
                    ans=temp;
                }
                while(1)
                {
                    tl++;
                    x_sum-=(b[tl].l-b[tl-1].r-1);
                    if(x_sum<=m)break;
                }
            }
        }
        temp=b[tr].r-b[tl].l+1+(m-x_sum);
        if(temp>ans)ans=temp;
        printf("%d\n",ans);
    }
}