algorithm - 准备一个时间表，以便在最短的时间内教授所有类(class)

Question

我遇到一个面试问题:
有一些教授，一些类(class)，还有一些学生。
每个教授只能教授一门类(class)。
每门类(class)都有固定的持续时间(例如10周)。
对于每位教授，您都会获得可用时间安排(假设每周)。
每个学生都有一个他想学习的类(class)列表。
只能有1:1的类(class)，即1个教授只能教1个学生。一名学生一次只能参加一门类(class)。教授必须一次性讲完一门类(class)。

您的目标是准备一个时间表，以便在最短的时间内教授所有类(class)。
我的方法:我提到这将通过图论来解决。比如从老师到类(class)或老师到学生建立有向边。但我无法完全解决它。
我的方法正确还是DP有问题？
伪代码或算法建议？

Answer 1

您被问到的问题是 schedulling problem ，这是一个动态规划问题。特别是，你的问题通常被称为FJm|brkdwn,pj=10|Cmax，可以如下推导:

• 有 m 台机器(教授)可以独立且以任何顺序处理部分工作(这里，工作是对学生的全部教学)。有些机器可能会处理工作的相同部分(相同的过程)
• 机器并非持续可用
• 部分工作(一门类(class))的持续时间为 10 周
• 您希望最大限度地缩短所有作业的完成时间

存在针对调度问题进行了很好优化的求解器，但我不确定将您的问题建模为调度问题并通过调度问题求解器处理它是否是您的求职面试官的意图。