貪心算法。如果一條線段在另一條線段的内部,那麼這條隻需要記錄下這條線段的長度後,就可以不予以考慮了。剩下的其他線段進行排序,然後考慮重合的部分就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
pair<int,int> a[+];
int main(){
int n,ans=-;
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a,a+n);
int last=a[].second;
for(int i=;i<n;i++){
if(a[i].second<last){
ans=max(ans,a[i].second-a[i].first);
}
else{
ans=max(ans,last-a[i].first);
last=a[i].second;
}
}
printf("%d\n",ans);
return ;
}