基于图算法的课堂调度

Question

这是我过去期中考试中的另一个问题，我应该给出一个正式的公式，描述所使用的算法，并证明其正确性。以下是问题所在：

这所大学正在设法安排不同的班级。每节课都有一个开始和结束时间。所有的课程都必须在星期五上课。只有两间教室可用。

帮助大学决定是否有可能在不引起任何时间冲突的情况下安排这些课程(即在同一教室安排两节课时重叠的班级)。

Answer 1

根据开始时间(O(nlogn))对类进行排序，然后按顺序(O(n))对它们进行遍历，记录开始和结束时间，并查找同时发生两个以上类的情况。

Answer 2

这不是二分图解的问题。谁告诉你的？

@Beta几乎是正确的。创建一个<START, time>和<END, time>对的列表。每个类在列表中有两对，一个开始，一个结束。

现在按时间对列表进行排序。或者，如果您愿意，将它们放在一个最小的堆中，这相当于堆排序。在相同的时间里，在开始之前把结束三倍放在前面。然后执行以下循环：

set N = 0
while sorted list not empty
  pop <tag, time> from the head of the list
  if tag == START
    N = N + 1
    if N > 2 return "can't schedule"
  else // tag == END
    N = N - 1
  end
end
return "can schedule"

您可以轻松地丰富算法，以返回两个以上类同时会话的时间段，返回这些类和其他有用的信息。

Answer 3

这确实是一个二部/双色问题。

假设每个类都是图的一个节点。现在，如果两个节点有时间重叠，则在它们之间创建一个边缘。现在，最后一个图，如果你可以双色这个图，那么它可以调度所有的类。否则就不会了。

如果您创建的图形是双色的，那么每个“黑色”节点将属于room1，每个“白色”节点将属于room2。