这道题作为NOI的题目还算是比较水的（虽然是第一题）
这道题是区间操作，不难看出可以用线段树做
【思路分析】
由于数据很大，我们先进行离散化，然后按区间长度排序并建一棵空树(维护当前区间重合部分最大值)
根据该线段树维护的结果 ，我们可以知道t[1].sum记录的是当前各条线段重合的最大值，只要t[1].sum大于m就符合题目要求了
接着我们采用尺取法,就是搞两个指针，一部分时间复杂度可以降到 O(n)并把总体时间复杂度从O(n^2) 降到了O(nlogn)
在此基础上，我们来求最小花费,我们先将排序好的线段一段一段丢到线段树里，当t[i].sum>=m时，我们将从头开始一段一段删掉，直到不满足条件
在此操作同时，我们维护ans最小值
具体见代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define M 5000005
using namespace std;
inline int read(){
char chr = getchar(); int f = 1,ans = 0;
while(!isdigit(chr)) {if(chr == '-') f = -1;chr = getchar();}
while(isdigit(chr)) {ans = ans * 10;ans += chr - '0';chr = getchar();}
return ans* f ;
}
void write(int x){
if(x < 0) putchar('-'),x=-x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n,m,c[M<<2],tot=0;
struct segment{int l,r,len;}a[M<<2]; //输入信息
struct node{int l,r,sum,lazy;int mid(){return l + r >> 1;} }t[M<<2];//线段树信息
bool cmp(const segment &a,const segment &b){return a.len<b.len; }//排序
void push_down(int i){//信息下传
if(t[i].lazy){
t[i << 1].lazy += t[i].lazy;
t[i << 1 | 1].lazy += t[i].lazy;
t[i << 1].sum += t[i].lazy;
t[i << 1 | 1].sum += t[i].lazy;
t[i].lazy = 0;
}
}
void push_up(int i){//信息上传
t[i].sum = max(t[i << 1].sum,t[i << 1 | 1].sum);
}
void build(int i,int l,int r){
t[i].l = l, t[i].r = r;
if(l == r) return;
int m = t[i].mid();
build(i << 1,l,m);
build(i << 1 | 1,m+1,r);
}//建树
void updata(int i,int l,int r, int v){
if(l <= t[i].l && t[i].r <= r){ t[i].lazy += v; t[i].sum += v; return; }
int m = t[i].mid();
push_down(i);
if(l <= m) updata(i << 1, l, r, v);
if(r > m) updata(i << 1 | 1, l, r, v);
push_up(i);
}//节点更新
int main(){
n = read();
m = read();
for(int i = 1;i <= n;i++)
a[i].l = read(),a[i].r = read(),a[i].len = a[i].r-a[i].l,c[++tot] = a[i].l,c[++tot] = a[i].r,c[++tot] = a[i].r + 1;
sort(a + 1,a + n + 1,cmp); sort(c + 1,c + tot + 1); tot=unique(c + 1,c + tot + 1) - c - 1;//去重
int minl = 0x3f3f3f3f,maxr = -0x3f3f3f3f;
for(int i = 1;i <=n ;i++)
a[i].l = lower_bound(c + 1,c + tot + 1 ,a[i].l) -c,minl = min(minl,a[i].l),
a[i].r = lower_bound(c + 1,c + tot+ 1 ,a[i].r) -c,maxr = max(maxr,a[i].r);
//阶段1、读入、排序处理、离散化
int l = 1,ans = 0x3f3f3f3f;
build(1,minl,maxr);
for(int i = 1 ;i <= n;i++){
updata(1, a[i].l, a[i].r, 1);
while(t[1].sum >= m){
ans=min(a[i].len - a[l].len,ans);
updata(1, a[l].l, a[l].r, -1);
l++;
}
}//阶段2 尺取法求出最小花费
if(ans == 0x3f3f3f3f) write(-1);
else write(ans);//输出
return 0;
}