← 返回题目列表

AtCoder · abc463_d

D. 最大化间隙

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 数轴上的布料。 的 i-th (1\le i\le N) 布覆盖间隔 \lbrack L _ i,R _ i\rbrack 上线了。 线上的一个点可能被两块或更多块布覆盖,或者没有任何一块布覆盖。

如果线上的某个点被两块布覆盖,则称两块布重叠。

对于两块不重叠的布料,定义它们的 距离 如下:

  • 的最小值 |p-q| 超过所有点 p 用一块布覆盖所有点 q 被另一块布覆盖。

对于 K 没有两个重叠的布料,定义它们的 分数 本实验的 作为所有这些布料对之间的最小距离。 选择时求最大可能的分数 K 布料来自 N 布料,确保所选布料中没有两块重叠。

如果无法选择 K 这样的布,输出 -1.

约束

  • 2\le K\le N\le2\times10 ^ 5
  • 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le 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,第二块布和第六块布之间的距离为 8,第四块布和第六块布之间的距离为 2,所以这个选择的分数是 2.

不可能选择三件得分为 3 或更多,所以输出 2.


示例输入 2

2 2
1 5
5 9

示例输出 2

-1

给定的两块布料重叠,因此不可能选择两块布料使得没有两块重叠。 因此,输出 -1.

请注意,第一块布料和第二块布料仅在单个点处重叠 5.


示例输入 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