BCS*_*BCS 5 language-agnostic theory algorithm
许多学生想要进入课堂的部分,有些已经注册了一个部分,但想要更改部分,所以他们都进入等候名单.只有当某人从该部分退出时,学生才能进入新的部分.没有学生愿意放弃他们已经在的部分,除非可以肯定进入他们正在等待的部分.每个部分的等待列表是先到先得.
让尽可能多的学生进入他们想要的部分.
所述问题可以快速转移到僵局场景.我的问题是; 有这个问题的已知解决方案吗？
一个简单的解决方案是依次取出每个部分并强制第一个学生从等待列表进入该部分,然后检查某人是否在事情解决时最终退出(部分数量为O(n)或更多).这可能适用于某些情况,但我认为可能有更好的选择,包括强制不止一个学生进入一个部分(学生数量为O(n)或更多)和/或一次操作多个部分(O (坏):-)
好吧，这只是归结为在类的有向图中寻找循环，对吧？每个链接都是一个想要从一个节点转到另一个节点的学生，只要你找到一个循环，你就删除它，因为这些学生可以互相解决他们的需求。当你的循环结束时，你就完成了。