python - 调度:最小化非重叠时间范围之间的差距

Question

使用 Django 开发一个小型日程安排 Web 应用程序，在该应用程序中，人们被分配特定的时间与他们的上级会面。员工存储为模型，与表示时间范围和他们有空的星期几的模型具有 OneToMany 关系。例如:

Bob: (W 9:00, 9:15), (W 9:15, 9:30), ... (W 15:00, 15:20)
Sarah: (Th 9:05, 9:20), (F 9:20, 9:30), ... (Th 16:00, 16:05)
...
Mary: (W 8:55, 9:00), (F 13:00, 13:35), ... etc

我的程序允许进行基本的日程安排设置，雇主可以在其中选择查看前 N 个可能的日程安排， session 之间的间隔最少，前提是他们在该周内至少会见所有员工一次。我目前正在生成所有可能的 session 排列，并过滤掉 session 时间重叠的时间表。有没有一种方法可以从 M 个可能的计划中生成前 N 个计划，而无需遍历所有 M 个可能性？

澄清:我们正试图获得任何给定日期的最小差距总和，所有天的总和。

Answer 1

我会使用搜索算法，例如 A-star ， 去做这个。图中的每个节点代表一个人的可用时间段，从一个节点到另一个节点的路径意味着 node_a 和 node_b 在部分时间表中。

另一种解决方案是创建一个图，其中节点是每个人的可用时间，如果与 node_a 关联的人与与 node_b 关联的人不同，则从 node_a 到 node_b 有一条边。每个节点的权重是与两个节点关联的时间之间的时间量。

创建此图后，您可以生成 minimum spanning tree 的变体从图中。该变体与 MST 的不同之处在于:

1. 如果与该节点关联的人尚未在 MST 中，您将仅向 MST 添加一个节点。
2. 当所有人都在 MST 中时，您就完成了 MST 的创建。

生成的最小生成树将表示单个计划。

要生成其他计划，请从您刚刚创建的计划中找到的图中删除所有边，然后从具有删除边的图中创建一个新的最小生成树。