Acwing 422.校门外的树

题目链接：

Acwing 422.校门外的树

思路：区间合并

1. 将所有重叠的区间进行合并。例如：[1,5]和[3,7] 合并为 [1,7]
2. 计算区间之间的距离大小：ed - st + 1
3. 总长度减去所有区间的大小。

区间合并的过程：

1. 将所有区间按照左边界进行从小到大的排序

2. 使用st指针表示左边界，ed 指针表示右边界

3. 然后遍历区间进行判断：
   如果第二个区间的左边界大于第一个区间的右边界，则说明这是两个完全分开的区间
   如果小于或等于第一个区间的右边界，则说明这两个区间的是有相交或相邻的

4. 如果是相交或相邻，就将第一个区间的右边界改成第二个区间的右边界，合并为一个区间

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 105;

vector<pair<int,int>> mes,res;
int l,m;

int main()
{
    cin>>l>>m;

    for(int i = 0; i < m; i ++)
    {
        int a ,b;
        cin>>a>>b;
        mes.push_back({a,b});
    }

    int st,ed;
    st = ed = -1;
    sort(mes.begin(),mes.end());
    for( int i = 0; i < m; i ++)
    {
        if(mes[i].first > ed){
            if(st != -1){
                res.push_back({st,ed});
            }
            st = mes[i].first;
            ed = mes[i].second;
        }else{
            ed = max(ed,mes[i].second);
        }
    }
    if(st != -1)res.push_back({st,ed});

    l++;
    for(int i = 0; i < res.size(); i++ )
    {
        l = l - (res[i].second - res[i].first) - 1;
    }
    cout<<l<<endl;
    return 0;
}