题目：

现在有 𝑛 个位置 1…𝑛 。

给𝑞个区间，请你选出选𝑞−2个，使得覆盖位置个数最大。

输入

第一行两个数n,q(3<=n,q<=5000)。 接下来q行，其中第i行两个数l[i],r[i]，表示第i个区间能覆盖所有满足l[i]<=x<=r[i]的位置x。

输出

一个数表示最大值。

输入样例

4 3
1 1
2 2
3 4

输出样例

2

题解：

暴力即可

代码：

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
struct point{
    int l,r;
};
point p[5010];
int sum[5010];
int main()
{
    int n,q;
    scanf("%d%d", &n, &q);
    for(int i = 0; i < q; i++)
        scanf("%d%d", &p[i].l, &p[i].r);
    int now = 0;
    for(int i = 0; i < q; i++)
        for(int j = p[i].l; j <= p[i].r; j++){
            if(sum[j] == 0)
                now++;
            sum[j]++;
        }
    int MIN = 99999;
    int o = 0;
    for(int i = 0; i < q; i++){
        int s = 0;
        for(int j = p[i].l; j <= p[i].r; j++){
            sum[j]--;
            if(sum[j] == 0)
                s++;
        }
        if(s < MIN)
            o = i;
        MIN = min(MIN,s);
        for(int j = p[i].l; j <= p[i].r; j++){
            sum[j]++;
        }
    }
    now -= MIN;
    MIN = 9999;
    for(int i = p[o].l; i <= p[o].r; i++)
        sum[i]--;
    for(int i = 0; i < q; i++){
        if(i  == o)
            continue;
        int s = 0;
        for(int j = p[i].l; j <= p[i].r; j++){
            sum[j]--;
            if(sum[j] == 0)
                s++;
        }
        MIN = min(MIN,s);
        for(int j = p[i].l; j <= p[i].r; j++){
            sum[j]++;
        }
    }
    printf("%d", now - MIN);
    return 0;
}