1

因此，我对使用尽可能少的教室安排可能重叠的 n 个活动的问题的解决方案有一些疑问。解决方案如下：

找到最少数量的教室来安排一组活动 S。为此，根据开始和结束时间有效地完成活动。维护两个教室列表：时间 t 繁忙的房间和时间 t 空闲的房间。当 t 是某个活动的开始时间时，将此活动安排到空闲房间并将房间移动到忙碌列表。同样，当活动停止时，将房间移动到空闲列表。最初从零房间开始。如果空闲列表中没有房间，则创建一个新房间。

该算法可以通过对活动进行排序来实现。在每个开始或结束时间，我们可以安排活动并在恒定时间内在列表之间移动房间。因此，总时间受排序支配，因此为 O(n lg n)。

我的问题是

1）首先，你如何同时开始和结束时间来完成活动？

2）我不太明白如何在恒定时间内在列表之间移动房间。如果您想将房间从忙碌列表移动到空闲列表，您是否不必遍历忙碌列表中的所有房间并查看哪些房间的结束时间已经过去？

3）在执行此操作以使其正常工作时，是否需要跟踪任何“状态”变量？

4

1 回答 1

2
  1. 该算法的工作方式是，您需要创建一个列表，其中包含每个开始时间的元素和每个结束时间的元素（如果有 n 个活动，则总共有 2n 个元素）。对这个列表进行排序。当结束时间和开始时间相等时，首先对结束时间进行排序——这将导致大厅的背靠背预订工作。
  2. 如果您使用链表来保存空闲和预订的大厅，您可以让您在步骤 1 中创建的元素保存指向活动结构的指针，并且该结构可以保存指向包含该活动所分配的大厅的列表元素的指针到。这最初为 NULL，并且当该大厅用于该活动时将采用一个值。然后，当该活动结束时，可以通过跟随来自活动结束元素的两个指针（首先到活动对象，然后从那里到大厅元素）在恒定时间内查找其大厅。
  3. 希望从上面的描述中可以清楚地看到这一点。
于 2012-11-27T09:57:57.743 回答