牛客跨年AK场-小sum的假期安排

链接：https://ac.nowcoder.com/acm/contest/3800/G
来源：牛客网

题目描述

小 sun 非常喜欢放假，尤其是那种连在一起的长假，在放假的时候小 sun 会感到快乐，快乐值等于连着放假的天数，现在小 sun 把他的安排表告诉你，希望你告诉他在他的安排表中， 他的最大快乐值。 

当某天没有安排的时候就是放假。

输入描述:

第一行两个数n,m，代表总共有n天，m个安排。

接下来有m行，每行是一个安排l,r，代表从第l天到第r天，小sun有安排了。

安排可能会重复。

输出描述:

输出一行，在这个安排表中，小sun最大的快乐值。

示例1

输入

复制

5 1
2 3

输出

复制

2

备注:

数据范围：

n≤1e9,m≤1e5
1≤l,r≤n

 

解题思路：主要考察结构体排序（先按开始时间排序）和模拟

 

 

 

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e5+10;
struct node{
    int l,r;
};
node a[maxn];
bool cmp(node a,node b){
    return a.l<b.l;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].l>>a[i].r;    
    }
    sort(a,a+m,cmp);
    int maxx=a[0].l-1,maxr=a[0].r;
    for(int i=1;i<m;i++){
        if(a[i].l>maxr){
            maxx=max(maxx,a[i].l-maxr);
        }
        maxr=max(maxr,a[i].r);
    }
    maxx=max(maxx,n-maxr);
    cout<<maxx<<endl;
    return 0;
}