TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

62.5% (5/8)

Submission's AC Ratio

28.6% (6/21)

Description

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

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

Input Format

輸入的第一行有一個整數n,代表遊輪的個數。
接下來有n行每一行分別有兩個整數Ai,Bi(Ai<=Bi),代表第i艘遊輪的到達和離開時間。
所有船隻的到達和離開時間都不會相等。

Output Format

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

Sample Input

4
1 30
5 10
6 12
11 20

Sample Output

2

Hints

佔總分30%的測試數據中 n<=15
佔總分100%的測試數據中 n<=1000,並且所有數字皆不超過1000000000。

Problem Source

原TIOJ1472 / CSAPC'08 Problem Setter: Seanwu

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144