“等待列表问题”

Question

许多学生希望进入某个班的各个部分，有些学生已经注册了一个部分但想要更改部分，因此他们都会进入等待列表。只有当有人从该部分丢失时，学生才能进入新的部分。除非可以确定进入他们正在等待的部分，否则没有学生愿意放弃他们已经进入的部分。每个部分的等待名单都是先到先得。

让尽可能多的学生进入他们想要的部分，你可以。

声明的问题可以很快转移到僵局情况。我的问题是;有没有已知的解决这个问题的方法？

---

一个平凡的解决办法是采取轮流各个部分，从等待列表中的第一个学生强行进入部分，然后检查是否有人最终辍学当事情都解决了（O（n）或更多关于部分的数量）。这对某些情况有效，但我认为可能会有更好的选择，包括迫使一个以上的学生加入某个部分（O（n）或更多的学生数）和/或一次操作多个部分（O （坏）:-)

Answer 1

那么，这只是归结为寻找类的有向图中的周期权？每个环节都是一个想要从一个节点走到另一个节点的学生，每当你找到一个循环时，你就会删除它，因为这些学生可以相互解决他们的需求。当你没有周期时，你就完成了。

Answer 2

这实际上是一个Graph问题。您可以将每个等待列表依赖关系视为有向图上的边。如果这个图形有一个循环，那么你有一个你描述的情况。一旦你确定了一个循环，你可以选择任何一点来通过“过度填充”其中一个类来“破坏”循环，并且你会知道事情会正确解决，因为图中有一个循环。

Answer 3

好的，让我们试试。我们有8名学生（1..8）和4个部分。每个学生都在一个部分，每个部分有2个学生的空间。大多数学生想要切换，但不是全部。

在下表中，我们看到学生当前的部分，他们需要的部分以及队列中的位置（如果有的话）。

+------+-----+-----+-----+ 
| stud | now | req | que | 
+------+-----+-----+-----+ 
| 1 | A | D | 2 | 
| 2 | A | D | 1 | 
| 3 | B | B | - | 
| 4 | B | A | 2 | 
| 5 | C | A | 1 | 
| 6 | C | C | - | 
| 7 | D | C | 1 | 
| 8 | D | B | 1 | 
+------+-----+-----+-----+ 

我们可以提出一个图这样的信息：

+-----+   +-----+   +-----+ 
| C |---[5]--->1| A |2<---[4]---| B | 
+-----+   +-----+   +-----+ 
    1    | |    1 
^    | |    ^
    |    [1] [2]    | 
    |    | |    | 
    [7]    | |    [8] 
    |    V V    | 
    |    2 1    | 
    |    +-----+    | 
    \--------------| D |--------------/ 
        +-----+ 

我们试图找到的空缺部分，但我们发现没有人。因为所有部分都已满，我们需要一个肮脏的窍门。因此，让我们随机选择一个非空的队列。在这种情况下，部分A并假设，它有一个额外的位置。这意味着学生5可以进入A部分，在C部分留下由学生7留下的空缺。这在D部分留下了学生2的空缺。我们现在在A部分有一个空缺。但是我们假设该部分A有一个额外的位置，所以我们可以消除这个假设并获得了一个更简单的图。

如果路径从未返回到A部分，请撤消移动并将A标记为无效的起点。重试另一节。 如果没有有效的部分，我们就完成了。

现在，我们有以下的情况：

+-----+   +-----+   +-----+ 
| C |   | A |1<---[4]---| B | 
+-----+   +-----+   +-----+ 
        |     1 
        |     ^
        [1]     | 
        |     | 
        |     [8] 
        V     | 
        1     | 
        +-----+    | 
        | D |--------------/ 
        +-----+ 

我们重复与另一随机部分的伎俩，这解决了图形。

如果您从当前尚未分配的几名学生开始，则会添加一个额外的虚拟部分作为其起点。当然，这意味着任何部分都必须有空缺，否则问题是不可解决的。

请注意，由于队列中的顺序，有可能没有解决方案。