← 返回题目
题库练习 Maximize the Gap
← 上一题 下一题 →

A7688 | Maximize the Gap

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

数轴上有 $N$ 块布料。第 $i$ 块布料（$1\le i\le N$）覆盖数轴上的区间 $\lbrack L _ i,R _ i\rbrack$。数轴上的某个点可能被两块或更多布料覆盖，也可能不被任何布料覆盖。

若数轴上存在某个点同时被两块布料覆盖，则称这两块布料**重叠**。

对于**不重叠**的两块布料，定义它们的**距离**如下：

* 对所有满足 $p$ 属于其中一块布料覆盖区间、$q$ 属于另一块布料覆盖区间的点对 $(p,q)$，取 $|p-q|$ 的最小值。

对于 $K$ 块互不重叠的布料，定义它们的**得分**为这 $K$ 块布料中所有两两之间的距离的最小值。请从 $N$ 块布料中选出 $K$ 块，使得任意两块均不重叠，并使所得分数尽可能大。

若无法选出满足条件的 $K$ 块布料，则输出 -1。

输入格式

输入从标准输入中以如下格式给出：

> $N$ $K$
> $L _ 1$ $R _ 1$
> $L _ 2$ $R _ 2$
> $\vdots$
> $L _ N$ $R _ N$

输出格式

输出答案。

输入输出样例

输入 #1
6 3
1 12
2 7
5 9
9 13
10 18
15 20
输出 #1
2
输入 #2
2 2
1 5
5 9
输出 #2
-1
输入 #3
20 5
169 748
329 586
529 972
432 520
408 587
138 250
114 656
299 632
755 984
404 772
155 506
832 854
353 465
374 387
384 567
555 631
428 951
104 705
405 530
102 258
输出 #3
35
C++ 编辑器
输入
输出