InterSections

题目描述

给你 $N$ 个区间，编号为 $1$ 到 $N$。区间 $i$ 为 $[L_i, R_i]$。 若且唯若满足 (l_a < l_b < r_a < r_b) 或 (l_b < l_a < r_b < r_a)，则称两个区间 $[l_a, r_a]$ 和 $[l_b, r_b]$ 相交。 定义 $f(l, r)$ 为与区间 $[l, r]$ 相交的区间 $i$ 的数量（$1 \leq i \leq N$）。 在所有满足 0 \leq l < r \leq 10^{9} 的整数对 $(l, r)$ 中，找到使 $f(l, r)$ 最大的那一对 $(l, r)$。如果存在多个这样的对，选择 $l$ 最小的那一对。如果仍存在多个，从中选择 $r$ 最小的那一对。（由于 0 \leq l < r，要回答的对 $(l, r)$ 是唯一确定的。）

输入格式

输入从标准输入按以下格式给出： $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

输出格式

按以下格式输出所求的对 $(l, r)$： $l$ $r$

5
1 7
3 9
7 18
10 14
15 20

4 11

11
856977192 996441446
298251737 935869360
396653206 658841528
710569907 929136831
325371222 425309117
379628374 697340458
835681913 939343451
140179224 887672320
375607390 611397526
93530028 581033295
249611310 775998537

396653207 887672321

提示

$1 \leq N \leq 10^{5}$ 0 \leq L_i < R_i \leq 10^{9} $(1 \leq i \leq N)$ 所有输入值均为整数。$f(l, r)$ 的最大值为 $4$，在所有达到 $f(l, r)=4$ 的对 $(l, r)$ 中，最小的 $l$ 为 $4$。满足 $f(l, r)=4$ 且 $l=4$ 的对如下五个：

$(l, r) = (4, 11)$ $(l, r) = (4, 12)$ $(l, r) = (4, 13)$ $(l, r) = (4, 16)$ $(l, r) = (4, 17)$

在这些中，最小的 $r$ 是 $11$，因此输出 $4$ 和 $11$。

标签: AtCoder|abc360F

来源

AtCoder|abc360F