PKU2376-Cleaning Shifts

題目：http://poj.org/problem?id=2376
有N(25000)個正整數對表示的線段[ai,bi]，
問至少選幾條才能完全覆蓋[1,T] ([1...1000000])
不可能覆蓋則輸出-1


程式碼：http://codepad.org/RxILK62E
經典greedy
關鍵點有「所有整數點都要蓋到」、「選任何線段的花費都一樣」
因為[1...T]所有點都要蓋到，沒有例外
所以我們不妨根據ai排序線段，從數字低位的區域開始決策

3 10
1 7
3 6
6 10
首先"1"一定要蓋到，滿足條件的就只有[1,7]一條非選不可
接下來要選的第二條線段，可以是起點1,2,3,4,5,6,7,8這幾種線段
(如果只剩下起點9這類可選，說明了"8"不可能蓋到，無解)

而起點[1,8]的線段這麼多條，該選哪一條呢？答案很明顯：終點最遠的那條

總結我們另外維護「已經蓋好的部分P」、「下次決策最優的終點Q」
每次只要P不夠了，就選一條延伸最遠加入答案(也就是取Q)
排序、貪心收工