题解 | #剩下的树#

#include <bits/stdc++.h>
#include <utility>
#include <vector>
using namespace std;
int main() {
    int L,M;
    while(cin>>L>>M)
    {
        vector<pair<int,int>> q;
        pair<int ,int>one;
        int Tree_num=L+1;//树的数量=马路长度+1
        int remove_num=0;//要移除的树的数量，初始为0
        int s,e;//s表示上一个要移除区间的起点，e表示上一个要移除区间的终点
        while(M--)//输入M个区间
        {
            cin>>one.first>>one.second;
            q.push_back(one);
        }
        //对区间按照起点排序
        sort(q.begin(),q.end(),[](const pair<int, int> &a,const pair<int, int> &b)
        {
            return a.first<b.first;
        });
        //先处理第一个区间
        s=q[0].first;
        e=q[0].second;
        remove_num+=(e-s+1);
        //处理后面的区间
        for(int i=1;i<q.size();i++)
        {
            //当前区间被上一个区间包含了
            if(q[i].second<=e) continue;
            //当前区间和上一个区间交叉
            if(q[i].first<=e&&q[i].second>e) 
            {
                remove_num+=(q[i].second-e);
                e=q[i].second;
            }
            //当前区间和上一个区间首尾不相连
            if(q[i].first>e)
            {
                s=q[i].first;
                e=q[i].second;
                remove_num+=(e-s+1);
            }
        }
        cout<<Tree_num-remove_num<<endl;
    }
}
// 64 位输出请用 printf("%lld")