牛客跨年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

输出

备注:

数据范围：

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

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

#pragma GCC optimize(2)

#include<bits/stdc++.h>

using namespace std;

inline int read() {int x=,f=;char c=getchar();while(c!='-'&&(c<''||c>''))c=getchar();if(c=='-')f=-,c=getchar();while(c>=''&&c<='')x=x*+c-'',c=getchar();return f*x;}

typedef long long ll;

const int maxn = 1e5+;

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=;i<m;i++){

        cin>>a[i].l>>a[i].r;

    }

    sort(a,a+m,cmp);

    int maxx=a[].l-,maxr=a[].r;

    for(int i=;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 ;

}