貪婪算法的實現

Question

所以我有一些問題解決了調度n個活動的問題，這些問題可能會重疊使用最少量的教室。解決的辦法是如下：

找到最小數量的教室安排一組活動S在要通過活動，根據開始和結束的時間做到這一點efefficiently 舉動。維護兩個教室列表：在時間t時繁忙的房間和在時間t時空閒的房間。當t是開始時間 某些活動將此活動安排到免費房間並將房間移至忙碌列表。 同樣，當活動停止時，將房間移至空​​閒列表。最初從零房間開始。如果 空閒列表中沒有房間，則創建一個新房間。

該算法可以通過排序活動來實現。在每個開始或結束時間，我們可以通過 安排活動並在固定時間之間移動列表間的房間。總的時間是 排序主導，因此是O（n lg n）。

我的問題是

1）首先，你如何通過活動移動雙方開始並在同一時間完成的時間？

2）我不太瞭解如何在固定時間內移動列表間的房間。如果您想將房間從繁忙列表移動到空閒列表，那麼您是否必須遍歷忙列表中的所有房間，並查看哪些房間的結束時間已經過去？

3）是否有任何'狀態'變量，我們需要跟蹤，這樣做，使其工作？

Answer 1

1. 算法的工作方式，你需要創建一個包含元素的每個開始時間列表以及每個結束時間的元素（因此，2n個元素總如果有N個活動）。對這個列表排序。當結束時間和開始時間相同時，首先對結束時間進行排序 - 這將導致大廳的緊接着的預訂工作。
2. 如果您使用鏈接列表來保存免費和預訂的大廳，您可以讓您在步驟1中創建的元素將指針保持回活動結構，並且此結構可以包含指向包含大廳的列表元素的指針活動分配給。最初這個數值爲NULL，並且當該大廳用於該活動時將會具有價值。然後，當活動結束時，可以通過跟隨活動結束元素（首先到活動對象，並從那裏到霍爾元素）的兩個指針，以恆定時間查看其大廳。
3. 這應該從上面的描述中清楚，希望。