回分類題庫
d045: 5.遊輪出航
關鍵字: 100年台中區複賽

測資點 : 3 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 49 Times / 41 Users | Submit : 174 Times / 50 Users | Accepted rate : 82%
題目加入時間 : 2012-07-06 14:43

Content: 简体中文

 高雄的愛河上有很多觀光遊輪,雖然遊輪可能分別屬於不同的船公司,但各船公司之間有個不成文的約定,當多艘遊輪要靠岸時,一種可能是直接停靠在岸邊的碼頭,讓遊客直接上岸;另一種方式是靠在已經停定位的船旁邊,遊輪可以一艘接著一艘並排停靠,離岸較遠的船上的遊客若要下船,則可以通過其它已經停妥的船到達岸上。不過有個限制,就是離岸較近的船不可以比離岸較遠的船先離開,不然離岸較遠的並排遊輪旅客就無法下船了。假定遊客上岸所需的時間可以忽略,請寫一程式解決以下問題。

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

Input:

輸入資料第一列有一個整數 N ,代表測試資料有幾組。
第二列有一個整數 M,代表第一組測試資料的觀光遊輪的總數。
接下來有 M 列每一列分別有兩個整數 Xi,Yi (Xi<Yi),代表第一組測試資料的第i艘觀光遊輪的到達和離開時間。
第二組以後的測試資料安排同上所述。

Output:

請輸出對每一組測試資料能讓所有船隻停靠的最少碼頭數目。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
2
5 8
0 10
4
3 28
10 25
5 11
7 15

Sample Output :

1
3

Hint :

註1:原官方測資第二組之第三小組為:

5
7  11
10  24
5  13
13  18
7  15

官方測資答案為 2,本站人工驗證後答案修正為 3。

註2:第三組測資由本站管理員自己產生,其 M 值為 20。

Author :

100年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum