分数: 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