algorithm - "Waiting lists problem"

Question

A number of students want to get into sections for a class, some are already signed up for one section but want to change section, so they all get on the wait lists. A student can get into a new section only if someone drops from that section. No students are willing to drop a section they are already in unless that can be sure to get into a section they are waiting for. The wait list for each section is first come first serve.

Get as many students into their desired sections as you can.

上述问题可能会很快演变成僵局。我的问题是；这个问题有已知的解决方案吗？

---

一个简单的解决方案是依次进入每个部分，并强制等待名单中的第一个学生进入该部分，然后检查是否有人在事情解决后退出(O(n) 或更多部分)。这适用于某些情况，但我认为可能有更好的选择，包括强制一个以上的学生进入一个部分(学生人数为 O(n) 或更多)和/或一次对多个部分进行操作(O (不好):-)

Answer 1

好吧，这只是在类的有向图中找到循环，对吗？每个链接都是一个想要从一个节点转到另一个节点的学生，每当你找到一个循环时，你就删除它，因为这些学生可以相互解决他们的需求。当你脱离循环时，你就完成了。