贪婪算法实现

Question

因此，我有一些问题是关于如何用尽可能少的教室来安排可能重叠的活动的问题。解决办法如下：

找出最少数量的教室来安排一组活动。根据开始和结束的时间，高效地完成活动。保持两张教室列表:时间t繁忙的房间和t时间空闲的房间。当t是一些活动的开始时间时，将这项活动安排到一个空闲的房间，并将房间移到繁忙的列表中。同样，当活动停止时，将房间移动到空闲列表。一开始是零房间。如果在空闲列表中没有房间，创建一个新房间。 该算法可以通过对活动排序来实现。在每个开始或结束的时间，我们可以安排活动，并在固定时间内在列表之间移动房间。因此，总时间受排序支配，因此是O(n lg n)。

我的问题是

首先，你是如何同时开始和完成活动的？

2)我不太明白如何能够在固定时间内在列表之间移动房间。如果你想把房间从繁忙的列表移到空闲的列表中，你不需要在繁忙列表中的所有房间中迭代，看看哪些房间的结束时间已经过去了？

3)是否有什么‘状态’变量，我们需要跟踪，同时，这样做，使它的工作？

Answer 1

1. 按照算法的工作方式，您需要创建一个列表，其中包含每个开始时间的一个元素和每个结束时间的一个元素(如果有n个活动，总共需要2n个元素)。对这份名单进行排序。当结束时间和开始时间相等时，首先对结束时间进行排序--这将导致对大厅的背靠背预订。
2. 如果使用链接列表来保存免费和预定的大厅，则可以让步骤1中创建的元素将指向活动结构的指针保留在后面，并且该结构可以保存指向包含此活动分配给的大厅的列表元素的指针。这将是空的最初，并将采取一个值时，该大厅是用于该活动。然后，当活动结束时，可以按照活动结束元素中的两个指针(首先指向活动对象，然后从活动对象到hall元素)，在恒定的时间内查找它的hall。
3. 希望从上面的描述中可以清楚地看到这一点。