分析
长度为l的路段总共有l+1棵树。
区间合并问题,把所有区间按左端点从小到大排序。
在更新右区间时要进行max()取最大值,防止这种情况发生:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int l,m,ans;
struct road{
int l,r;
bool operator < (const road& p) //排序函数,按左端点从小到大排序
{
if(l!=p.l) return l<p.l;
return r<p.r;
}
}a[110];
int main()
{
cin>>l>>m;
for(int i=0;i<m;i++)
{
cin>>a[i].l>>a[i].r;
}
sort(a,a+m);
int sl=a[0].l,sr=a[0].r;
for(int i=1;i<m;i++)
{
if(a[i].l<=sr) sr=max(a[i].r,sr); //max取最大的右端点
else{
ans+=(sr-sl+1);
sl=a[i].l;
sr=a[i].r;
}
}
ans+=(sr-sl+1);
cout<<(l+1-ans); //总数减去要砍掉的树
return 0;
}