UOJ Logo Universal Online Judge

UOJ

#222. 【NOI2016】区间

附件下载 统计

在数轴上有 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],...,[l_n,r_n]$。现在要从中选出 $m$ 个区间,使得这 $m$ 个区间共同包含至少一个位置。换句话说,就是使得存在一个 $x$,使得对于每一个被选中的区间 $[l_i,r_i]$,都有 $l_i \le x \le r_i$。

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$,即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案,输出 $−1$。

输入格式

第一行包含两个正整数 $n,m$,用空格隔开,意义如上文所述。保证 $1 \le m \le n$。

接下来 $n$ 行,每行表示一个区间,包含用空格隔开的两个整数 $l_i$ 和 $r_i$ 为该区间的左右端点。

输出格式

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

样例一

input

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

output

2

explanation

样例图

如图,当 $n=6,~m=3$ 时,花费最小的方案是选取 $[3,5]$、$[3,4]$、$[1,4]$ 这三个区间,他们共同包含了 $4$ 这个位置,所以是合法的。其中最长的区间是 $[1,4]$,最短的区间是 $[3,4]$,所以它的花费是 $(4−1)−(4−3)=2$。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

所有测试数据的范围和特点如下表所示:

测试点编号 $n$ $m$ $l_i,r_i$
1$20$$9$$0 \le l_i \le r_i \le 100$
2$10$
3$199$$3$$0 \le l_i \le r_i \le 100000$
4$200$
5$1000$$2$
6$2000$
7$199$$60$$0 \le l_i \le r_i \le 5000$
8$200$$50$
9$0 \le l_i \le r_i \le 10^9$
10$1999$$500$$0 \le l_i \le r_i \le 5000$
11$2000$$400$
12$500$$0 \le l_i \le r_i \le 10^9$
13$30000$$2000$$0 \le l_i \le r_i \le 100000$
14$40000$$1000$
15$50000$$15000$
16$100000$$20000$
17$200000$$0 \le l_i \le r_i \le 10^9$
18$300000$$50000$
19$400000$$90000$
20$500000$$200000$

时间限制:$3\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载