algorithm - 两行拟合间隔

我有点纠结于这个问题：
给出一个n个课程的列表，我从Si开始到Fi结束，
找到一个适合2个大厅课程表的算法，其中
每个大厅一次只能容纳一个课程。
我考虑了用每个大厅的最优解来求解，每次在大厅中放置最小Fi，然后移除在最小Fi之前开始的所有Si，递归地保持到课程结束，然后对大厅2执行最优解。
发现每个大厅的最优解并不能同时给出两者的最优解。
编辑：
最优的解决方案是以最小的时间复杂度满足两个大厅中的大多数课程的解决方案。
例如：课程列表：
{（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中，其他三个课程在hall2中。

最佳答案

你的攻击是好的，但是太窄了：你需要用所有的大厅来完成，用最早可用的开始时间填满一个大厅，而不是在你开始另一个之前完全完成一个大厅。
制作一个包含每个大厅的可用（开始，结束）时间和已分配给该大厅的hall_list课程的sched。

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号大厅的第一个课程。
价值精化：
如上所述，在每次迭代中，选择每小时值最高的最早课程。1小时的课程值为1；5小时的课程值为1/5。
问题：
这也失败了；（0,5]被留到最后，这时就没有合适的了。
最佳搭配：
选择开始时间最早的课程；如果打成平手，则选择结束时间最早的课程。
这恰好适用于给定的情况。事实上，如果已知存在一个适合所有类的解，那么这将在线性时间中找到解。如果按开始时间对课程进行迭代，就更容易了。
然而，如果最优解没有放置所有的课程，那么这很容易失败再添加两个类(1,2], (2,3]，此算法将看不到它们应该替换2号大厅中的(0,5]。
更深入的攻击
正如@marcin已经在一个删除的答案中指出的那样，这个一般情况并不是一个简单的问题。为了保证在任何情况下都能得到最优解，您需要对布局树进行深入搜索编写一个递归例程来尝试所有的可能性。使用动态编程：记住你的结果，这样你就不会做多余的计算输入大厅剩余的开始时间（已排序）和剩余的课程列表。
在预处理过程中，您可以做一些有助于实际示例的事情。例如，一个孤立的短类序列可以融合成一个具有更高值的公共分配。在给定的示例中，您将把(0,1], (1,2], (2,3]融合到(0,3]中。（4,7）中的完成时间阻止您使用(5, 6], (6, 8]执行此操作。
这有助于你找到解决办法吗？

关于algorithm - 两行拟合间隔，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47583169/