#UVa中文翻譯:10020-Minimal coverage(最小覆蓋區間)

灆洢 2014-08-19 15:25:51

問題

給予許多利用[Li,Ri]所表示的小線段(在X坐標軸的整數點上),你必須選擇最少的線段讓它們能夠完整地覆蓋起[0,M]區間。

輸入

第一行有一個數字,表示的是會有幾筆測試資料,後面會跟著一行空白行。

輸入中每一筆測試資料會包含一格數字M(1<=M<=5000),後面跟著一對一對的”Li Ri“(|Li|, |Ri|<=50000, i<=100000),每一對會在不同行。每一筆測試資料最後會以”0 0″作為完結。

每一筆測試資料之間會用一行隔開。

輸出

對於每筆測試資料,你的程式要在第一行輸出能覆蓋[0,M]區間最少要用到的線段數量是多少。接著數行是每一段線段的座標,依據它們的最左邊來排序(Li),並且線段的表示方式要與他們在輸入中的是相同的格式。至於”0 0″這一對則不能被輸出出來。如果[0,M]區間不能被給予的線段給覆蓋,你的程式必須要輸出”0″(不用雙引號)。

在兩個測試資料的輸出的中間印出一行空白行隔開。

範例輸入

2

1
-1 0
-5 -3
2 5
0 0

1
-1 0
0 1
0 0

範例輸出

0

1
0 1

翻譯:灆洢。若翻譯有任何錯誤,歡迎底下留言告知,感謝!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料