Description：

有 $N$ 个区间。要从中选出 $M$ 个区间，使得这 $M$ 个区间共同包含至少一个位置。求所有合法方案中最长区间长度减去最短区间长度的最小值。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

看到题目区间最大最小能想到双指针，但是这题的双指针非常不同，因为他双指针扫的顺序并不是按数轴上的顺序的，原因是这样扫每个点区间没有单调性，正确的做法是先按区间长度排序，这样第一个区间就是最短的，最后一个就是最长的，然后按顺序把他们依次加入，当有一个点被覆盖了 $\geqslant m$ 次，这个可以用线段树来统计，就依次弹掉之前加入的，用最后一次弹掉的更新答案，直到不存在一个点被覆盖 $\geqslant m$ 次，因为之前的线段和之后的一定不会产生一个优于当前答案的解，然后就没了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 500010

struct seg

{

	int l,r;

}s[MAXN];

bool cmp_len(seg a,seg b){return a.r - a.l < b.r - b.l;}

int b[MAXN << 1],tot = 0;

int cur = 0;

struct node

{

	int lc,rc;

	int maxv,tag;

}t[MAXN << 2];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag != 0)

	{

		t[t[rt].lc].maxv += t[rt].tag;t[t[rt].lc].tag += t[rt].tag;

		t[t[rt].rc].maxv += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

		t[rt].tag = 0;

	}

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].maxv += k;t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

int main()

{ 

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= n;++i)

	{

		s[i].l = read();s[i].r = read();

		b[++tot] = s[i].l;b[++tot] = s[i].r;

	}

	sort(b + 1,b + 1 + tot);

	cur = unique(b + 1,b + 1 + tot) - b - 1;

	build(root,1,cur);

	sort(s + 1,s + 1 + n,cmp_len);

	register int ans = 0x3f3f3f3f;

	for(register int i = 1,j = 1;i <= n;++i)

	{

		add(root,lower_bound(b + 1,b + 1 + cur,s[i].l) - b,lower_bound(b + 1,b +  + cur,s[i].r) - b,1,1,cur);

		register int last = 0;

		for(;t[root].maxv >= m;++j)

		{

			last = j;

			add(root,lower_bound(b + 1,b + 1 + cur,s[j].l) - b,lower_bound(b + 1,b + 1 + cur,s[j].r) - b,-1,1,cur);

		}

		if(last != 0)

			ans = min(ans,(s[i].r - s[i].l) - (s[last].r - s[last].l));

	}

	if(ans != 0x3f3f3f3f)printf("%d\n",ans);

	else cout << -1 << endl;

	return 0;

}