思路
求的是n个区间中的k个区间的最大交集。先以左端排序,再设计一个右端点的小根堆。这样把以左端从小到大排序的线段,装入k个到小根堆,用堆中最小的右端减去最大的左端就是这k个线段最大的交集。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n,k,ans;
const int N=1e5+10;
struct node{
int l,r;
}inte[N];
bool cmp1(const node &a,const node &b){
return a.l<b.l;
}
struct cmp2{
bool operator()(const node &a,const node &b){
return a.r>b.r;
}
};
priority_queue<node,vector<node>,cmp2> sk;
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d%d",&inte[i].l,&inte[i].r);
}
sort(inte,inte+n,cmp1);
for(int i=0;i<k;i++) sk.push(inte[i]);
ans=sk.top().r-inte[k-1].l;
for(int i=k;i<n;i++){
sk.push(inte[i]);
sk.pop();
ans=max(ans,sk.top().r-inte[i].l);
}
printf("%d\n",ans);
return 0;
}