最大化间距AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)There are $N$ cloths on a number line. The $i$-th $(1\le i\le N)$ cloth covers the interval $\lbrack L _ i,R _ i\rbrack$ on the line. A point on the line may be covered by two or more cloths, or not covered by any cloth.
数轴上有 $N$ 块布料。第 $i$ 块布料 $(1\le i\le N)$ 覆盖数轴上的区间 $\lbrack L _ i,R _ i\rbrack$。数轴上的一个点可能被两块或更多布料覆盖，也可能不被任何布料覆盖。AI (CI翻译)
Two cloths are said to overlap if some point on the line is covered by both of those cloths.
如果数轴上存在某个点同时被两块布料覆盖，则称这两块布料重叠。AI (CI翻译)
For two cloths that do not overlap, define their distance as follows:
对于两块不重叠的布料，定义它们之间的距离如下：AI (CI翻译)
- The minimum value of
$|p-q|$over all points$p$covered by one cloth and all points$q$covered by the other cloth.
- 对所有分别被这两块布料覆盖的点
$p$和$q$，取$|p-q|$的最小值。
For $K$ cloths no two of which overlap, define their score as the minimum distance among all pairs of those cloths. Find the maximum possible score when choosing $K$ cloths from the $N$ cloths so that no two of the chosen cloths overlap.
对于任意 $K$ 块两两不重叠的布料，定义它们的得分为其中任意两块布料之间距离的最小值。请从 $N$ 块布料中选出 $K$ 块，且任意两块都不重叠，使得得分最大，并求出该最大得分。AI (CI翻译)
If it is impossible to choose $K$ such cloths, output -1.
如果无法选出满足条件的 $K$ 块布料，请输出 -1。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$2\le K\le N\le2\times10 ^ 5$$0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)$- All input values are integers.
$2\le K\le N\le2\times10 ^ 5$$0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N K
L _ 1 R _ 1
L _ 2 R _ 2
\vdots
L _ N R _ NN K
L _ 1 R _ 1
L _ 2 R _ 2
\vdots
L _ N R _ NOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
6 3
1 12
2 7
5 9
9 13
10 18
15 20
2
2 2
1 5
5 9
-1
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
35
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。