1472 . 遊輪 Boat

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

36.0% (9/25)

Submission's AC Ratio

29.2% (61/209)

Tags

CSAPC 2008-CSAPC

Description

埃及的尼羅河上有很多遊輪，雖然可能分別屬於不同的公司，但之間有個不成文的默契。當多艘遊輪要靠岸時，一種可能是直接停靠在岸邊的碼頭，另一種方式是靠在已經就位的船旁邊。它們可以一艘接著一艘並排起來，離岸較遠的船上的遊客若要下船，則可以通過其它的船到達岸上。不過有個限制，就是離岸較近的船不可以比離岸較遠的船先離開，不然就會被卡住出不去了。

給所有船隻的到達和離開時間，問岸邊最少需要幾個碼頭，才能讓所有的船有辦法靠岸。

Input Format

輸入的第一行有一個整數 $N$，代表遊輪的個數。
接下來有 $N$ 行每一行分別有兩個整數 $A_i, B_i(A_i \leq B_i)$，代表第i艘遊輪的到達和離開時間。
所有船隻的到達和離開時間都不會相等。
$N \leq 24$
$A_i \leq B_i \leq 100$

Output Format

請輸出能讓所有船隻靠岸的最少碼頭數。

Sample Input 1

4
1 30
5 10
6 12
11 20

Sample Output 1

2

Hints

Problem Source

原TIOJ1472 / CSAPC'08 Problem Setter: Seanwu
test data updated by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0~7 $N\leq 10$ 30
2 0~13 $N \leq 18$ 40
3 0~19 $N \leq 24$ 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 512000 65536 1 2 3
1 1000 512000 65536 1 2 3
2 1000 512000 65536 1 2 3
3 1000 512000 65536 1 2 3
4 1000 512000 65536 1 2 3
5 1000 512000 65536 1 2 3
6 1000 512000 65536 1 2 3
7 1000 512000 65536 1 2 3
8 1000 512000 65536 2 3
9 1000 512000 65536 2 3
10 1000 512000 65536 2 3
11 1000 512000 65536 2 3
12 1000 512000 65536 2 3
13 1000 512000 65536 2 3
14 1000 512000 65536 3
15 1000 512000 65536 3
16 1000 512000 65536 3
17 1000 512000 65536 3
18 1000 512000 65536 3
19 1000 512000 65536 3
Submit
Back to Top