思路
这道题我刚开始的思路，是按照l为第一关键字，r为第二关键字从小到大排完序以后，二分答案，后来wa掉了，其实就是排完序的结果未必能够连续使用。
因为如果区间非常长的小
比如k=3
1 9
5 6
5 9
6 10
如果是用二分的话5 6是没有办法排掉的
因此我们可以用优先队列，将l从小到大进行遍历，然后将右端点r压入优先队列，将小的先弹出，因为最后的答案一定是所有区间的交集，那么l是所有区间的左端点的最右边那个，右端点就是最左边那个，所以我们遍历左端点，然后保证了当前的端点已经是我们判断的端点最右边那个，当然了，右边的也一定说明最小的那个。
其实这里还有一个疑问，就是如果当前入堆的刚好是要弹出的，那么我们做了一次运算，是不是会有问题，其实答案是不会的，因为，如果当前要弹出的话，我们确保了l比上次还要大，但是r却和上一次一样，因此这个一定不是最大值。
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r,id;
}s[2102100];
int ans[2102100];
int n,k;
int ll,rr;
int lans,rans;
int cmp(node x,node y){
//if(x.l==y.l)return x.r<y.r;
return x.l<y.l;
}
int check(int mid){
int lmax=-1e9;
int rmin=1e9;
for(int i=1;i<=n-k+1;i++){
ll=i,rr=i+k-1;
lmax=-1e9;
rmin=1e9;
for(int j=ll;j<=rr;j++){
lmax=max(lmax,s[j].l);
rmin=min(rmin,s[j].r);
}
if(rmin-lmax+1>=mid)return true;
}
return false;
}*//*
int bsearch(int l,int r){
int mid;
while(l<r){
mid=l+r+1>>1;
if(check(mid)){
lans=ll;
rans=rr;
l=mid;
}
else r=mid-1;
}
return l;
}*//*
int main(){
cin>>n>>k;
priority_queue<int>q;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
s[i]={l,r,i};
}
sort(s+1,s+1+n,cmp);
int ans=0;
int l=1e-9,r=1e9;
for(int i=1;i<=n;i++){
q.push(-s[i].r);
if(q.size()>k)q.pop();
if(q.size()==k){
int tot=-q.top();
tot-=s[i].l-1;
if(tot>ans){
ans=tot;
l=s[i].l,r=-q.top();
}
}
}
cout<<ans<<endl;
if(ans==0){
for(int i=1;i<=k;i++)cout<<i<<" ";
return 0;
}
int tot=0;
for(int i=1;i<=n;i++){
if(s[i].l<=l&&s[i].r>=r){
cout<<s[i].id<<" ";
tot++;
}
if(tot==k)break;
}
}