2

有没有我可以用来解决以下问题的通用算法：

鉴于：

背景：一个月，有 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)
{
  ...
}
4

2 回答 2

4

将每个事件拆分为两个标记为“开始”和“结束”的时间点（保持指向原始事件的反向指针），按时间对所有点进行排序 - 打破平局，使“结束”同时出现在“开始”之前。

现在检查点（按照上面定义的顺序），在每个“开始”上分配第一个空闲号码，并在每个“结束”上释放相关号码。

例子：

活动：9AM-5PM、9AM-2PM、5PM-6PM、3PM-6PM

时间点排序表：

(9AM 开始事件1), (9AM 开始事件2), (2PM 结束事件2), (3PM 开始事件4), (5PM 结束事件1), (5PM 开始事件3), (6PM 结束事件3), (6PM 结束事件4)

加工：

(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-14T15:25:14.953 回答
0

这几乎是我在本科期间学习的算法课的逐字记录。基于最早开始时间和最短持续时间分配房间的贪心算法是最优的。这种最优性的证明留作练习，以防止教授不及格读者。:)

于 2013-02-15T14:56:18.690 回答