基本思路:合并有交集的区间,然后将原区间归零,再统计非零区间长度(=r-l+1)。
然后以为#1含有[0,0]导致被坑,于是将清零的区间改为[-114,514]依然错误。说明不是此原因。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
ll l;
ll r;
};
node a[N];
bool cmp(node a,node b)
{
return a.l<b.l;
}
int main()
{
int n;
cin>>n;
ll x,y,le=0;
for(int i=1; i<=n; i++)
{
scanf("%lld %lld",&x,&y);
a[i].l=x;
a[i].r=y;
}
sort(a+1,a+n,cmp);
for(int i=1; i<=n-1; i++)
{
if(a[i+1].l<=a[i].r && a[i+1].r>=a[i].r)
{
a[i+1].l=a[i].l;
a[i].l=0;
a[i].r=0;
}
else if(a[i+1].l<=a[i].r)
{
a[i+1].l=a[i].l;
a[i+1].r=a[i].r;
a[i].l=0;
a[i].r=0;
}
}
for(int i=1; i<=n; i++)
{
if(a[i].l!=0 && a[i].r!=0)
le+=a[i].r-a[i].l+1;
}
cout<<le;
return 0;
}