時隙分配算法

-1

是否有一個通用的算法，我可以使用，以解決以下問題：時隙分配算法

考慮：

背景：一個月，其中有0到1000的事件（任意數量真的）。每個事件都有一個開始日期和結束日期。事件發生在房間中，一次一個（不重疊，但是隨後的事件可以分享彼此的結束日期和開始日期）。房間數量不限。

挑戰：爲事件分配房間，使主持月事件所需的房間數量保持最小。

雖然完整的解決方案是高度讚賞，我正在尋找任何方向，聰明的想法。

class Event: 
- int Id; 
- DateTime StartDate; 
- DateTime EndDate 

class Allocation: 
- int EventId 
- int RoomId

所以我在尋找：

// roomIds is Enumerable.Range(1, int.MaxValue) 
IEnumerable<Allocation> GetAllocations(IEnumerable<Event> events, IEnumerable<int> roomIds, int year, int month) 
{ 
    ... 
}

來源

2013-02-14 user1514042

這是功課嗎？你有什麼嘗試？ – MoonKnight 2013-02-14 15:22:43

我認爲主要想法是，如果你不想找到最佳性能，就是使用遞歸（或堆棧）來測試每種可能的組合。然後簡單地過濾出使用最少房間的工作組合。 – 2013-02-14 15:24:01

不管它是或不是，只要堅持主題。我試過貪婪的算法來分配變化，正在尋找方面的意見。 – user1514042 2013-02-14 15:24:44

分割的每一個事件分爲兩個時間點標記爲「開始」和「結束」（背部保持指向原始事件），排序所有的時間點 - 打破關係，以便'結束'在同一時間開始。

現在仔細點（按照上面定義的順序），在每個「開始」上分配第一個空閒數字並釋放每個「結束」上的相關數字。

實施例：

活動：9 AM-5PM，9 AM-2PM，5 PM-6PM，3 PM-6PM

排序時間點的表：

（上午9時開始事件1），（上午9時開始EVENT2 ），（下午2點結束事件2），（3PM啓動EVENT4），（5PM端事件1），（5PM開始EVENT3），（下午6點結束EVENT3），（下午6點結束EVENT4）

處理：

(9AM start event1) - assign room 1 to event1 
(9AM start event2) - assign room 2 to event2 
(2PM end event2) - free room 2 
(3PM start event4) - assign room 2 to event4 
(5PM end event1) - free room 1 
(5PM start event3) - assign room 1 to event3 
(6PM end event3) - free room 1 
(6PM end event4) - free room 2

來源

2013-02-14 15:25:14

有些事件會有差距，因爲房間沒有被任何事件佔用。如何回合下一個發現的事件是否適合一個月內？ – user1514042 2013-02-14 15:28:55

@ user1514042免費房間會導致事件發生缺口？我不明白。在你分配房間之後，如果有必要的話，你可以按月分組這些事件（除非我誤解了你寫的內容。） – 2013-02-14 15:38:58

確實如此。 – user1514042 2013-02-14 15:55:03

這幾乎是我在本科期間學習的算法類的逐字。基於最早的開始時間和最短的持續時間分配房間的貪婪算法是最優的。這種最優性的證明是作爲一個練習，讓教授不要讓讀者不喜歡。 :)

來源

2013-02-15 14:56:18

時隙分配算法

回答

相關問題