← 返回题目列表

AtCoder · abc360_f

I. 交叉路口

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

分数: 550 点

问题陈述

你被给予 N 间隔编号 1 to N。间隔 i is [L_i, R_i].

两个间隔 [l_a, r_a] 和 [l_b, r_b] 据说 相交 当且仅当它们满足 (l_a < l_b < r_a < r_b) or (l_b < l_a < r_b < r_a).

定义 f(l, r) 作为间隔数 i (1 \leq i \leq N) 与区间相交 [l, r].

在所有对中 整数 (l, r) 满意 0 \leq l < r \leq 10^{9},找到这对 (l, r) 最大化 f(l, r)。如果有多个这样的对,则选择最小的一对 l。如果还有多对,则选择最小的一对 r 其中。 (因为 0 \leq l < r,一对 (l, r) 要回答的问题是唯一确定的。)

约束

  • 1 \leq N \leq 10^{5}
  • 0 \leq L_i < R_i \leq 10^{9} (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

打印所寻找的对 (l, r) 采用以下格式:

l r

示例输入 1

5
1 7
3 9
7 18
10 14
15 20

示例输出 1

4 11

的最大值 f(l, r) is 4,并且在对中 (l, r) 实现 f(l, r) = 4,最小的 l is 4。成对的 (l, r) 满足 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 is 11,所以打印 4 和 11.


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