164 . 拉麵烹調

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

23.5% (4/17)

Tags

ioicamp ioicamp-2022

Description

BB 是一個拉麵愛好者。因為疫情的關係，他沒辦法去他做喜愛的拉麵店內用了，於是只好買冷凍包來維持他的拉麵生活。

屋漏偏逢連夜雨，BB 家的冷凍庫壞掉了，現在所有的拉麵都會開始解凍。由於每款拉麵的成分不同，因此他們會在不同的時間點完成解凍。根據 BB 對拉麵的深刻了解，第 $i$ 款拉麵如果放在室溫下，會在 $a_i$ 的時間點完成解凍，如果放在冷藏，會在 $b_i$ 的時間點完成解凍。（由於 BB 買了某些很特別的拉麵，不保證 $a_i\leq b_i$。）拉麵解凍完就要立刻吃，但是 BB 可以選擇要把哪些拉麵放進冷藏。

作為一個拉麵愛好者，BB 堅持要在每款拉麵完成解凍的當下馬上食用，但 BB 依然希望吃每款拉麵的間隔盡量久，這樣他才能好好的回味前一碗麵的味道。因此他會把一些拉麵放進冷藏，其餘放在室溫，使得他吃任兩款拉麵的時間間隔最小值能夠盡量大。請問他吃任兩款拉麵的時間間隔最小值最大是多少？

Input Format

第一行有一個正整數 $N$，代表 BB 有 $N$ 款拉麵。

接下來 $N$ 行每行有兩個正整數 $a_i,b_i$，代表第 $i$ 款拉麵如果放在室溫下，會在 $a_i$ 的時間點完成解凍，如果放在冷藏則會在 $b_i$ 的時間點完成解凍。

  • $2\le N\le 10^ 4$
  • $1\le a_i, b_i\le 10^ 9$

Output Format

輸出一個非負整數，代表 BB 吃任兩款拉麵的時間間隔最小值最大可以是多少。

Sample Input 1

3
1 3
2 5
1 9

Sample Output 1

4

Sample Input 2

5
2 2
2 2
2 2
2 2
2 2

Sample Output 2

0

Hints

Problem Source

IOICamp 2022 Day2 pD

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~29 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
Submit
Back to Top