题目描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。

我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。

这些区域用它们在数轴上的起始点和终止点表示。

已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。

现在要把这些区域中的树（包括区域端点处的两棵树）移走。

你的任务是计算将这些树都移走后，马路上还有多少棵树。

样例

输入

500 3
150 300
100 200
470 471

输出

298

所谓的区间的合并，不过是先对区间进行sort排序（左端点或者右端点），之后不断的对左端点和右端点进行更新，来计算端点直接的空隙。

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=110;
int n,m;
PII w[N];

bool cmp(PII a,PII b)
{
    return a.x<b.x;    //按左端点进行排序
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    cin>>w[i].x>>w[i].y;
    sort(w,w+m,cmp);

    int res=0;
    int l=w[0].x,r=w[0].y;
    for(int i=1;i<m;i++)
    {
        if(w[i].x<=r)  r=max(r,w[i].y);
        else 
        {
            res+=r-l+1;   //上一个的右端点和这个左端点的差值，因为每个点都有树，所以+1；
            l=w[i].x,r=w[i].y;  //更新左端点和右端点
        }
    }
    res+=r-l+1;//最后一个区间
    cout<<n+1-res<<endl;//总的树-移走的树
    return 0;
}