A7688. Maximize the Gap
编程题
入门
知识点
题目描述
数轴上有 $N$ 块布料。第 $i$ 块布料（$1\le i\le N$）覆盖数轴上的区间 $\lbrack L _ i,R _ i\rbrack$。数轴上的某个点可能被两块或更多布料覆盖，也可能不被任何布料覆盖。
若数轴上存在某个点同时被两块布料覆盖，则称这两块布料**重叠**。
对于**不重叠**的两块布料，定义它们的**距离**如下：
* 对所有满足 $p$ 属于其中一块布料覆盖区间、$q$ 属于另一块布料覆盖区间的点对 $(p,q)$，取 $|p-q|$ 的最小值。
对于 $K$ 块互不重叠的布料，定义它们的**得分**为这 $K$ 块布料中所有两两之间的距离的最小值。请从 $N$ 块布料中选出 $K$ 块，使得任意两块均不重叠，并使所得分数尽可能大。
若无法选出满足条件的 $K$ 块布料，则输出
若数轴上存在某个点同时被两块布料覆盖，则称这两块布料**重叠**。
对于**不重叠**的两块布料，定义它们的**距离**如下：
* 对所有满足 $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$
> $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
说明/提示
**样例 1 解释：**
选择第 2、第 4 和第 6 块布料，这三者两两互不重叠。第 2 块与第 4 块布料之间的距离为 $2$，第 2 块与第 6 块布料之间的距离为 $8$，第 4 块与第 6 块布料之间的距离为 $2$，因此该选择的得分为 $2$。
无法选出三块布料使得其得分达到 $3$ 或更高，故输出
**样例 2 解释：**
给定的两块布料相互重叠，因此不可能选出两块互不重叠的布料。故输出
注意：第 1 块与第 2 块布料仅在单点 $5$ 处重叠。
### 约束条件
* $2\le K\le N\le2\times10 ^ 5$
* $0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)$
* 所有输入值均为整数。
选择第 2、第 4 和第 6 块布料，这三者两两互不重叠。第 2 块与第 4 块布料之间的距离为 $2$，第 2 块与第 6 块布料之间的距离为 $8$，第 4 块与第 6 块布料之间的距离为 $2$，因此该选择的得分为 $2$。
无法选出三块布料使得其得分达到 $3$ 或更高，故输出
2。**样例 2 解释：**
给定的两块布料相互重叠，因此不可能选出两块互不重叠的布料。故输出
-1。注意：第 1 块与第 2 块布料仅在单点 $5$ 处重叠。
### 约束条件
* $2\le K\le N\le2\times10 ^ 5$
* $0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)$
* 所有输入值均为整数。