天天看點

51Nod1091 線段的重疊

貪心算法。如果一條線段在另一條線段的内部,那麼這條隻需要記錄下這條線段的長度後,就可以不予以考慮了。剩下的其他線段進行排序,然後考慮重合的部分就可以了。

#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 ;
}