https://ac.nowcoder.com/acm/contest/1085/A

description：

一共有n天m个安排，每个安排从l~r天，问最长的休息时间是多少

solution：

一开始想着各种数组标记，mapset乱搞，线段树，由于天数到了1e9，所以计算区间大小肯定要O1得到，正解是我们以左边界为第一关键字，右边界为第二关键字进行排序，遍历所有选项计算区间取最大值。难点就在于如何正确得到区间长度，假设当前存在一个区间l,r是有工作的，我们就有n - r （右端点到右边界） 和 l 左边界和左端点距离。
排序后设定初始的边界
我们每次只计算靠左边的距离，当所有靠左边的计算完后，就只剩下靠右边的距离n - r 对答案取max就好
其中 a[i].l - r + 1 左边界是当前的左边界 而右边界r是上次最大的r 他们之间的距离就是空闲时间

code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1e5 + 50;

struct node{
    int l,r;
};

node a[N];

bool cmp(node a,node b){
    if(a.l != b.l){
        return a.l < b.l;
    }
    return a.r < b.r;
}

int main(){
    ios::sync_with_stdio(0);
    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 res = a[0].l - 1;//初始左边界到端点距离
    int r = a[0].r;

    for(int i = 1;i < m;i ++){
        if(a[i].l > r){
            res = max(res,a[i].l - r + 1);// 当前左边界 - 之前最大右边界 +  1
        }
        r = max(a[i].r,r);
    }
    res = max(res,n - r);

    cout << res << '\n';

    return 0;
}