本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-10 19:43:15

思路

选择的 $m$ 个区间的花费是其中最长的区间减去最短区间，那么，为了使花费最小，这 $m$ 个区间在长度排名上是要连续的。
所以先对这 $n$ 个区间排序，然后枚举每一个要选的区间。每枚举一个区间，都将区间中每一个点覆盖次数加一，然后判断是否有一个点的覆盖次数超过了 $m$ 次，那么就开始更新答案，具体细节：

1. 删除最先加入且还没被删的区间
2. 更新答案
3. 如果仍然有一个点的覆盖次数超过了 $m$ 次，go to step 1

至于区间覆盖次数记录，使用线段树记录即可，另外注意要离散化。

另注：
如果到最终也没有更新答案，那么无解

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=5e5+5;
	\/\/---------IO----------
	int n,m;
	struct Section
	{
		int l,r,len;
		bool operator <(const Section& b)
		{
			return len<b.len;
		}
	}sec[maxn<<3];
	int cnt;
	int all[maxn<<3];
	\/\/------Trie--------
	struct Trie
	{
		int max,lazy;
	}trie[maxn<<3];
	inline void push_down(int node)
	{
		if(trie[node].lazy==0)return;
		trie[node<<1].lazy+=trie[node].lazy;
		trie[node<<1].max+=trie[node].lazy;
		trie[node<<1|1].lazy+=trie[node].lazy;
		trie[node<<1|1].max+=trie[node].lazy;
		trie[node].lazy=0;
	}
	inline void push_up(int node)
	{
		trie[node].max=max(trie[node<<1].max,trie[node<<1|1].max);
	}
	void Modify(int node,int _l,int _r,int l,int r,int val)
	{
		if(_r<l||_l>r)
		{
			return;
		}
		if(_l>=l&&_r<=r)
		{
			trie[node].lazy+=val;
			trie[node].max+=val;
			return;
		}
		push_down(node);
		int mid=(_l+_r)>>1;
		if(l<=mid)Modify(node<<1,_l,mid,l,r,val);
		if(r>mid)Modify(node<<1|1,mid+1,_r,l,r,val);
		push_up(node);
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		int li,ri;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&li,&ri);
			all[++cnt]=li;
			all[++cnt]=ri;
			sec[i].l=li;
			sec[i].r=ri;
			sec[i].len=sec[i].r-sec[i].l;
		}
		sort(all+1,all+cnt+1);
		cnt=unique(all+1,all+cnt+1)-all-1;
		for(int i=1;i<=n;i++)
		{
			sec[i].l=lower_bound(all+1,all+cnt+1,sec[i].l)-all;
			sec[i].r=lower_bound(all+1,all+cnt+1,sec[i].r)-all;
		}
		sort(sec+1,sec+n+1);
		int fir=1;
		int ans=0x3f3f3f3f;
		for(int i=1;i<=n;i++)
		{
			Modify(1,1,cnt,sec[i].l,sec[i].r,1);
			while(trie[1].max>=m)
			{
				ans=min(ans,sec[i].len-sec[fir].len);
				Modify(1,1,cnt,sec[fir].l,sec[fir].r,-1);
				fir++;
			}
		}
		if(ans==0x3f3f3f3f)
		{
			printf("-1");
		}
		else
		{
			printf("%d",ans);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}