題目：http://poj.org/problem?id=3190
有N(50000)頭牛，每頭牛都有產奶時段[A,B]
每次奶牛都要自己用一個牛欄來產奶，當她產完以後、其他牛才可以重複使用
問最少要幾個牛欄、並且輸出任意一種分配方案
程式碼：codepad掛了，待補
首先很顯然地對開始時間Ai進行排序，依次考慮
我們每次都希望知道哪個牛欄是最快空出來的，盡量把牛補進去
這就可以開一個heap來維護
對於每頭牛，檢查heap頂端(目前最快空出的牛欄)
如果可以就塞牛、不可以就另開一個牛欄，中間紀錄各牛進了編號幾號就AC了
沒有留言:
張貼留言