时隙分配算法

-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

时隙分配算法

回答

相关问题