algorithm - 在最少数量的槽中安排作业/间隔

Question

我认为这个问题类似于加权间隔调度问题，但略有不同。

假设您有一个具有开始时间和结束时间的类次 s，该类次从 s.start 开始有 n 个空位到s.end。时隙是从 s.start 到 s.end 的可填充时间范围。您有 m 个间隔，其中每个间隔都有开始和结束时间。将间隔分配给槽，这样您就可以使用最少数量的槽。只要没有重叠间隔，就可以将间隔分配给时隙。给定的间隔已知适合给定数量的槽(但它们不必填充槽)。一旦将间隔 i 分配给一个时隙，该时隙就已填充了 i 的时间范围。

我写了一个 jsbin，它为此做了一个蛮力算法，但它是 O(n!) 或更糟，因为它检查每个可能的间隔序列，并试图贪婪地将它们放入第一个没有冲突。

http://jsbin.com/bixalabume/1/edit?js,console (我称间隔为“段”。)

这个问题是否可以在合理的时间内解决？我觉得有一个 DP 解决方案，但想不出一个。

我不是特别擅长这种编程，但是这里有一些类似的问题，我看了但无法理解:

• https://cs.stackexchange.com/questions/42008/weighted-interval-scheduling-with-m-machines - 类似但我的问题没有加权间隔(我认为)
• Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction) (我认为这更复杂，因为它具有可变的插槽时间，而我的插槽是相等的时间)

Answer 1

这可以通过图形着色来解决，其中对于每个间隔你创建一个顶点，并且一个顶点与另一个顶点有链接，前提是相应的间隔重叠。这会自动使干扰图成为区间图，非常容易着色，甚至无需构建图形:按开始时间对区间进行排序，并将它们一个接一个地插入它们可以进入的第一个槽中。这将是最佳的，因为为了在插入时需要新的颜色 k，必须是 k - 1 颜色在间隔开始时被占用的情况插入，所以至少 k 间隔在那个时候重叠，所以它们不可能被赋予少于 k 的颜色。