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 点

时间点排序表:

(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