贪婪算法的实现

Question

所以我有一些问题解决了调度n个活动的问题，这些问题可能会重叠使用最少量的教室。解决的办法是如下：

找到最小数量的教室安排一组活动S在要通过活动，根据开始和结束的时间做到这一点efefficiently 举动。维护两个教室列表：在时间t时繁忙的房间和在时间t时空闲的房间。当t是开始时间 某些活动将此活动安排到免费房间并将房间移至忙碌列表。 同样，当活动停止时，将房间移至空​​闲列表。最初从零房间开始。如果 空闲列表中没有房间，则创建一个新房间。

该算法可以通过排序活动来实现。在每个开始或结束时间，我们可以通过 安排活动并在固定时间之间移动列表间的房间。总的时间是 排序主导，因此是O（n lg n）。

我的问题是

1）首先，你如何通过活动移动双方开始并在同一时间完成的时间？

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

3）是否有任何'状态'变量，我们需要跟踪，这样做，使其工作？

Answer 1

1. 算法的工作方式，你需要创建一个包含元素的每个开始时间列表以及每个结束时间的元素（因此，2n个元素总如果有N个活动）。对这个列表排序。当结束时间和开始时间相同时，首先对结束时间进行排序 - 这将导致大厅的紧接着的预订工作。
2. 如果您使用链接列表来保存免费和预订的大厅，您可以让您在步骤1中创建的元素将指针保持回活动结构，并且此结构可以包含指向包含大厅的列表元素的指针活动分配给。最初这个数值为NULL，并且当该大厅用于该活动时将会具有价值。然后，当活动结束时，可以通过跟随活动结束元素（首先到活动对象，并从那里到霍尔元素）的两个指针，以恒定时间查看其大厅。
3. 这应该从上面的描述中清楚，希望。