c# - 时隙分配算法

Question

是否有一个通用算法可以用来解决以下问题:

给定:

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

Answer 1

将每个事件分成两个标记为“开始”和“结束”的时间点(保留指向原始事件的后向指针)，按时间对所有点进行排序 - 打破平局，以便“结束”在同一时间出现在“开始”之前。

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

示例:

事件:上午 9 点至下午 5 点、上午 9 点至下午 2 点、下午 5 点至下午 6 点、下午 3 点至下午 6 点

时间点排序表:

(上午 9 点开始事件 1)、(上午 9 点开始事件 2)、(下午 2 点结束事件 2)、(下午 3 点开始事件 4)、(下午 5 点结束事件 1)、(下午 5 点开始事件 3)、(下午 6 点结束事件 3)、(下午 6 点结束事件 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