题意

有 $n$ 个区间，选 $m$ 个，使得最大区间长度减去最小区间长度最小。

$n\leq5\times 10^5,m\leq2\times10^5$ 。

题解

按区间长度排序，然后双指针扫区间，右指针扫当前选的大区间，左指针扫小区间。对于当前已选数量，用线段树维护。

代码

const int N = 5e5 + 3;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	struct SGT {
		struct node {
			int l, r, val, tag;
		} t[N << 4];
#define lson p << 1
#define rson p << 1 | 1
		void build (int p, int l, int r) {
			t[p].l = l, t[p].r = r;
			if (t[p].l == t[p].r) {
				t[p].val = 0;
				return ;
			}
			int mid = (t[p].l + t[p].r) >> 1;
			build (lson, l, mid);
			build (rson, mid + 1, r);
			t[p].val = 0;
		}
		void pushdown (int p) {
			if (!t[p].tag) return;
			t[lson].tag += t[p].tag;
			t[lson].val += t[p].tag;
			t[rson].tag += t[p].tag;
			t[rson].val += t[p].tag;
			t[p].tag = 0;
			return ;
		}
		void modify (int p, int l, int r, int val) {
			if (l <= t[p].l && t[p].r <= r) {
				t[p].tag += val;
				t[p].val += val;
				return ;
			}
			pushdown(p);
			int mid = (t[p].l + t[p].r) >> 1;
			if (l <= mid) modify(lson, l, r, val);
			if (r > mid) modify(rson, l, r, val);
			t[p].val = max(t[lson].val, t[rson].val);
		}
	}t;
	struct Segment {
		int l, r, len;
		Segment (int l = 0, int r = 0):l(l), r(r) { len = r - l; }
		bool operator < (const Segment &a) const {
			return len == a.len? l < a.l: len < a.len;
		}
	}sg[N];
	int b[N << 1], tot;
	int ans = 0x3f3f3f3f;
	int main() {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) {
			int l = Read(), r = Read();
			sg[i] = Segment(l, r);
			b[++tot] = l; b[++tot] = r;
		}
		sort (sg + 1, sg + 1 + n);
		sort (b + 1, b + 1 + tot);
		tot = unique(b + 1, b + 1 + tot) - b - 1;
		for (int i = 1; i <= n; i++) {
			sg[i].l = lower_bound(b + 1, b + 1 + tot, sg[i].l) - b;
			sg[i].r = lower_bound(b + 1, b + 1 + tot, sg[i].r) - b;
		}
		t.build(1, 1, (N - 3) << 1);
		for (int l = 1, r = 1; r <= n; r++) {
			t.modify(1, sg[r].l, sg[r].r, 1);
			for (; t.t[1].val >= m && l <= r; l++) {
				ans = min(ans, sg[r].len - sg[l].len);
				t.modify(1, sg[l].l, sg[l].r, -1);
			}
		}
		if (ans == 0x3f3f3f3f) ans = -1;
		printf ("%d\n", ans);
		return 0;
	}
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}