algorithm - 两行拟合间隔

Question

我有点卡在这个问题上:

Given a list of n courses, where course i starts at Si and ends at Fi, find an algorithm that fits the courses' schedule in 2 halls where as each hall accommodates only one course at a time.

我想过用每个大厅的最优解来解决，你每次把最小的 Fi 放在大厅里，然后删除所有在最小 Fi 之前开始的 Si，递归地保持直到类(class)结束。然后为二号厅发现每个大厅的最优解并不能同时给出两个大厅的最优解。

编辑:

一个最优解是一个时间复杂度最小的适合两个馆内最多类(class)的解

例如:类(class)列表:

{(0,1], (0,5], (1,2], (2,3], (4,7], (5,6], (6,8]}

一个大厅应该包含:

{(0,1], (1,2], (2,3], (4,7]}

第二个:

{(0,5], (5,6], (6,8]}

但是，我上面的算法开始适合第一个大厅；当它到达

hall1 = {(0,1], (1,2], (2,3]}
courses = {(0,5], (4,7], (5,6], (6,8]}

算法选择最早的结束时间，加入(5,6]；最优解要求(4,7]在hall1，其他三个类(class)在hall2。

Answer 1

您的攻击很好，但范围太窄:您需要对所有 大厅进行此操作，用最早可用的开始时间填充一个大厅，而不是在开始另一个大厅之前完全完成一个大厅。

制作一个hall_list，其中包含每个大厅的可用(开始、结束)时间以及已经分配给该大厅的计划类(class)。

place_class (hall_list, course_list)
    start = earliest available start time of any hall
    if no such time, return present solution

    hall = the hall with that time
    course_ok = filter course_list for classes where S(i) <= start
    choose i from course_ok with the earliest F(i)

    append i to hall.sched
    remove i from course_list
    hall.start = F(i)

    place_course(hall_list, course_list)

---

这不适用于您发布的示例；同样的缺陷正在等待，但它首先遇到碎片问题:(1, 2] 将是第一个进入大厅 2 的类(class)。

值(value)细化:

如上所述，在每次迭代中，选择每小时值最高的最早类(class)。 1 小时的类(class)的值为 1； 5 小时的类(class)有 1/5 的值(value)。

问题:

这也失败了； (0,5] 留到最后，到那时已经不合适了。

---

最佳匹配细化:

选择开始时间最早的类(class)；如果平局，选择最早的结束时间。

这恰好适用于给定的情况。事实上，如果已知存在适合所有类别的解决方案，这将在线性时间内找到解决方案。如果您遍历按开始时间排序的类(class)，那就更容易了。

但是，如果最优解没有放置所有类(class)，那么这很容易失败。再添加两个类 (1,2], (2,3]，此算法将看不到它们应该替换 2 号厅中的 (0,5]。

---

深度攻击

正如@Marcin 在已删除的答案中指出的那样，这种一般情况不是一个简单的问题。为了保证在任何情况下都能找到最佳解决方案，您需要对布局树进行深入搜索。编写一个递归程序来尝试所有的可能性。使用动态规划:记住你的结果，这样你就不会进行多余的计算。键入大厅的剩余开始时间(排序)和剩余类(class)列表。

有您可以在预处理中做的事情可能有助于实际示例。例如，可以将一个孤立的短类序列融合到一个具有更高值的公共(public)分配中。在您给出的示例中，您会将 (0,1], (1,2], (2,3] 融合到 (0,3] 中。完成时间in (4,7] 会阻止您(简单地)使用 (5, 6], (6, 8] 执行此操作。

这是否有助于您找到解决方案？