Embedded Files
zerojudge網址：https://zerojudge.tw/ShowProblem?problemid=j608
解題策略：排序+multiset+二分搜尋(lower_bound)
活動依照結束時間由小到大排序，若結束時間相同，可以不用依照開始時間排序。機器結束時間依序加入multiset會形成平衡的binary search tree，使用二分搜尋lower_bound找出第一個iterator(it)大於等於新活動的開始時間，(--it)就會找到最後一個機器結束時間小於新活動開始時間的機器，該機器執行新活動，更新結束時間到multiset。
範例輸入 #1
5 1
0 2 1 3 4
2 3 5 4 6
範例輸出 #1
2
範例輸入 #3
2 1
1 2
2 3
範例輸出 #3
1
範例輸入 #2
8 2
3 1 4 3 7 2 2 5
5 3 7 4 8 7 4 6
範例輸出 #2
5
C++參考程式
Python程式碼(使用bisect取代multiset)
Page updated
Google Sites
Report abuse