原题链接
解析
笔者原本的思路是按照左端点排序考虑交点，但是发现无法快速处理出极差；还想过了不考虑交点直接做。
为什么不再回溯一层呢？
由于要求长度的极差，所以考虑将区间按照长度排序。按照这个顺序依次覆盖每个区间对应的点，当某个点被覆盖的次数 \(\ge m\) 时统计答案，统计时维护一个指针 \(pos\) 指向最早加入的区间，利用 \(len_i-len_{pos}\) 更新答案并消除第 \(pos\) 个区间的贡献，然后右移 \(pos\)，直到没有一个点被覆盖次数 \(\ge m\)。
可以利用线段树来维护区间最大覆盖次数。
需要离散化。
时间复杂度 \(O(n\log n)\)。
代码
注意判无解。
/*
*/
#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5e5 + 5,M = 2e5 + 5,mod = 998244353;
pii s[N];
int len[N],mx[N << 1 << 2],tag[N << 1 << 2];
bool cmp(pii a,pii b){return a.second - a.first < b.second - b.first;
}
void push_up(int p){mx[p] = max(mx[ls(p)],mx[rs(p)]);
}
void add_tag(int p,int k){tag[p] += k;mx[p] += k;
}
void push_down(int p){if(!tag[p]) return;add_tag(ls(p),tag[p]);add_tag(rs(p),tag[p]);tag[p] = 0;
}
void modi(int p,int l,int r,int L,int R,int k){if(l > R || r < L) return;if(l >= L && r <= R){add_tag(p,k);return;}push_down(p);modi(ls(p),l,mid,L,R,k),modi(rs(p),mid + 1,r,L,R,k);push_up(p);
}
int main(){ios::sync_with_stdio(false);cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);int n,m;cin>>n>>m;vector<int> v;for(int i=1;i<=n;i++){cin>>s[i].first>>s[i].second; v.push_back(s[i].first);v.push_back(s[i].second);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int siz = v.size();sort(s + 1,s + n + 1,cmp);int l = 1;int res = 2e9;for(int i=1;i<=n;i++){len[i] = s[i].second - s[i].first;s[i].first = lower_bound(v.begin(),v.end(),s[i].first) - v.begin() + 1;s[i].second = lower_bound(v.begin(),v.end(),s[i].second) - v.begin() + 1;modi(1,1,siz,s[i].first,s[i].second,1);while(mx[1] >= m){res = min(res,len[i] - len[l]);modi(1,1,siz,s[l].first,s[l].second,-1);l++;}}cout<<(res == 2e9 ? -1 : res);return 0;
}