TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

37.5% (9/24)

Submission's AC Ratio

29.3% (61/208)

Tags

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