利用区间合并的思想求解

解题思路: 将区间合并之后即可解决区间重合问题

注意事项: 注意数据类型

参考代码:

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

typedef pair<int,int> PII;

const int N=100010;

int n;

vector<PII> segs;

void merge(vector<PII> &segs)

{

    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st=-2e9,ed=-2e9;

    for(auto seg:segs)

    {

        if(ed<seg.first)

        {

            if(st!=-2e9) res.push_back({st,ed});

            st=seg.first,ed=seg.second;

        }

        else ed=max(ed,seg.second);

    }

    if(st!=-2e9) res.push_back({st,ed});

    segs=res;

}

int main()

{

    int len,n;

    cin>>len>>n;

    for(int i=0;i<n;i++)

    {

        int l,r;

        cin>>l>>r;

        segs.push_back({l,r});

    }

    merge(segs);

    int sum=0;

    for(auto seg:segs)

    {

        sum+=(seg.second-seg.first+1);

    }

    cout<<(len+1)-sum<<endl;

    return 0;

}