Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。

Input

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n
接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。
N<=500000,M<=200000,0≤li≤ri≤10^9

Output

只有一行，包含一个正整数，即最小花费。

Sample Input

6 3
3 5
1 2
3 4
2 2
1 5
1 4

Sample Output

2


【解题方法】

           容易想到先按照区间的长度来排序之后，明显有单调性，要统计直接用双指针移动维护答案就好了。用线段树维护一下出现次数。

【AC 代码】

//
//Created by just_sort 2016/8/19
//All Rights Reserved
//

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000010;
const int inf = 0x3fffffff;
struct query{
    int l,r,len;
    bool operator<(const query &rhs) const{
        return len<rhs.len;
    }
}q[maxn*2];
struct node{
    int l,r;
    int maxx,lazy;
}Tree[maxn*4];
vector<int>xs;
void pushup(int rt)
{
    Tree[rt].maxx=max(Tree[rt*2].maxx,Tree[rt*2+1].maxx);
}
void pushdown(int rt)
{
    if(Tree[rt].lazy){
        Tree[rt*2].lazy+=Tree[rt].lazy;
        Tree[rt*2+1].lazy+=Tree[rt].lazy;
        Tree[rt*2].maxx+=Tree[rt].lazy;
        Tree[rt*2+1].maxx+=Tree[rt].lazy;
        Tree[rt].lazy=0;
    }
}
void Build(int l,int r,int rt)
{
    Tree[rt].l=l,Tree[rt].r=r;
    Tree[rt].lazy=0,Tree[rt].maxx=0;
    if(l==r) return ;
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
}
void update(int L,int R,int v,int rt)
{
    if(L==Tree[rt].l&&Tree[rt].r==R){
        Tree[rt].lazy+=v;
        Tree[rt].maxx+=v;
        return ;
    }
    pushdown(rt);
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) update(L,R,v,rt*2);
    else if(L>mid) update(L,R,v,rt*2+1);
    else{
        update(L,mid,v,rt*2);
        update(mid+1,R,v,rt*2+1);
    }
    pushup(rt);
}
int main()
{
    xs.clear();
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].len=q[i].r-q[i].l;
        xs.push_back(q[i].l);
        xs.push_back(q[i].r);
    }
    sort(xs.begin(),xs.end());
    xs.resize(unique(xs.begin(),xs.end())-xs.begin());
    int key=xs.size();
    for(int i=1; i<=n; i++){
        q[i].l=lower_bound(xs.begin(),xs.end(),q[i].l)-xs.begin()+1;
        q[i].r=lower_bound(xs.begin(),xs.end(),q[i].r)-xs.begin()+1;
    }
    sort(q+1,q+n+1);
    //cout<<key<<endl;
    Build(1,key,1);
    //two pointers
    int ans=inf,i,j=0;
    for(i=1; i<=n; i++){
        while(j<n&&Tree[1].maxx<m) j++,update(q[j].l,q[j].r,1,1);
        if(Tree[1].maxx>=m) ans = min(ans,q[j].len-q[i].len);
        else break;
        update(q[i].l,q[i].r,-1,1);
    }
    if(ans==inf) ans=-1;
    printf("%d\n",ans);
    return 0;
}