Ural 1424 - Minibus

題目連結: http://acm.timus.ru/problem.aspx?space=1&num=1424
CUHK training時隨手選出來的題目, 想不到也挺符合我們這星期的大主題greedy algorithm

題意很簡單, 就是generalized的activity selection
由每個時間只可選一個interval改為每段時間最多可以選M個interval, 問最多可以選多少個interval
同時可以有M個interval, 一共可選擇的interval共有N個

細心想想, 就會知道原來的greedy方法仍然是正確的: 跟據結束時間排序之後貪心地選
一開始想到做M次activity selection, 但這樣的time complexity會是O(MK), 應該會超時
再想就覺得可以維護一個list儲着最後M個interval的結束時間, 然後選最接近而少於現在的starting time的interval去replace

既然要用Binary Search Tree, 就先去想想可不可以用STL的set
發現我們需要的操作有insert, delete, 和query largest integer which is less than or equal to k
STL明顯可以做到這些操作, 由於裏面的數有可能重覆, 所以需要用multiset
留意STL的Binary Search Tree也有upper_bound和lower_bound的功能
只要想清楚upper_bound和lower_bound的分別就可以漂亮地解決
假如想不清楚的話都可以用iterator去在BST中微調而找出想要的element

這題也算是練習Greedy和STL中比較有趣的題目