AT_abc360_f [ABC360F] 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)$ 为满足 $1 \leq i \leq N$ 且区间 $[l, r]$ 与区间 $i$ 相交的 $i$ 的个数。

请在所有满足 $0 \leq l < r \leq 10^9$ 的整数对 $(l, r)$ 中，找到使 $f(l, r)$ 取得最大值的 $(l, r)$，并在这些对中选择 $l$ 最小的。如果仍有多个解，则选择 $r$ 最小的（由于 $0 \leq l < r$，答案是唯一的）。

输入格式

输入通过标准输入给出，格式如下：

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

请输出答案对 $(l, r)$，格式如下：

$l$ $r$

输入输出样例 #1

输入 #1

5
1 7
3 9
7 18
10 14
15 20

输出 #1

4 11

输入输出样例 #2

输入 #2

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

输出 #2

396653207 887672321

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $0 \leq L_i < R_i \leq 10^9$（$1 \leq i \leq N$）
• 输入均为整数

样例解释 1

$f(l, r)$ 的最大值为 $4$，且使 $f(l, r)=4$ 的 $(l, r)$ 中，$l$ 的最小值为 $4$。满足 $f(l, r)=4$ 且 $l=4$ 的 $(l, r)$ 有以下 $5$ 种：

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

其中 $r$ 的最小值为 $11$，因此输出 $4$ 和 $11$。

由 ChatGPT 4.1 翻译