algorithm - 日历调度算法

Question

我正在寻找一种算法，如果给定一组包含开始时间、结束时间、类型和 id 的项目，它将返回一组适合在一起的所有项目集(没有重叠时间，所有类型都在集)。

S = [("8:00AM", "9:00AM", "Breakfast With Mindy", 234),
     ("11:40AM", "12:40PM", "Go to Gym", 219),
     ("12:00PM", "1:00PM", "Lunch With Steve", 079),
     ("12:40PM", "1:20PM", "Lunch With Steve", 189)]

Algorithm(S) => [[("8:00AM", "9:00AM", "Breakfast With Mindy", 234),
                  ("11:40AM", "12:40PM", "Go to Gym", 219),
                  ("12:40PM", "1:20PM", "Lunch With Steve", 189)]]

谢谢!

Answer 1

这可以使用 graph theory 解决.我将创建一个数组，其中包含按开始时间和结束时间排序的项目，开始时间相等:(向示例中添加了更多项目):

no.:  id: [ start  -   end  ] type
---------------------------------------------------------
 0:  234: [08:00AM - 09:00AM] Breakfast With Mindy
 1:  400: [09:00AM - 07:00PM] Check out stackoverflow.com
 2:  219: [11:40AM - 12:40PM] Go to Gym
 3:   79: [12:00PM - 01:00PM] Lunch With Steve
 4:  189: [12:40PM - 01:20PM] Lunch With Steve
 5:  270: [01:00PM - 05:00PM] Go to Tennis
 6:  300: [06:40PM - 07:20PM] Dinner With Family
 7:  250: [07:20PM - 08:00PM] Check out stackoverflow.com

之后，我将创建一个包含数组编号的列表。可能是下一个项目的最少项目。如果没有下一项，则添加 -1:

 0 |  1 |  2 |  3 |  4 |  5 |  6 |  7
 1 |  7 |  4 |  5 |  6 |  6 |  7 | -1

使用该列表可以生成 directed acyclic graph .每个顶点都连接到从下一项开始的顶点。但是对于已经是它们之间的顶点的顶点，则不会产生边。我会试着用例子来解释。对于顶点 0，下一项是 1。所以边是 0 -> 1。从 1 开始的下一项是 7，这意味着从顶点 0 连接的顶点的范围现在是 1 to (7-1) .因为顶点 2 在 1 到 6 的范围内，所以生成了另一条边 0 -> 2 并且范围更新为 1 to (4-1) (因为 4 是 2 的下一项)。因为顶点 3 在 1 到 3 的范围内，所以又生成了一条边 0 -> 3。那是顶点 0 的最后一条边。必须继续所有顶点都指向这样的图:



直到现在我们都在 O(n2) 中。之后，可以使用 depth first search 找到所有路径-like 算法，然后从每个路径中消除重复的类型。
对于该示例，有 4 个解决方案，但没有一个具有所有类型，因为该示例不可能执行 Go to Gym , Lunch With Steve和 Go to Tennis .

此外，这种对所有路径的搜索的最坏情况复杂度为 O(2n)。例如，下图有 2n/2 条从起始顶点到结束顶点的可能路径。


(来源: archive.org)

可以进行更多优化，例如在搜索所有路径之前合并一些顶点。但这永远不可能。在第一个示例中，顶点 3 和 4 不能合并，即使它们是相同的类型。但是在最后一个示例中，如果顶点 4 和顶点 5 属于同一类型，则它们可以合并。这意味着您选择哪种事件并不重要，两者都是有效的。这可以显着加快所有路径的计算。

也许还有一种聪明的方法可以更早地考虑重复类型以消除它们，但如果您想要所有可能的路径，最坏的情况仍然是 O(2n)。

编辑1:

可以确定是否存在包含所有类型的集合并在多项式时间内获得至少一个这样的解。我找到了一个最坏情况时间为 O(n4) 和 O(n2) 空间的算法。我将举一个新的例子，它有一个所有类型的解决方案，但更复杂。

no.:  id: [ start  -   end  ] type
---------------------------------------------------------
 0:  234: [08:00AM - 09:00AM] A
 1:  400: [10:00AM - 11:00AM] B
 2:  219: [10:20AM - 11:20AM] C
 3:   79: [10:40AM - 11:40AM] D
 4:  189: [11:30AM - 12:30PM] D
 5:  270: [12:00PM - 06:00PM] B
 6:  300: [02:00PM - 03:00PM] E
 7:  250: [02:20PM - 03:20PM] B
 8:  325: [02:40PM - 03:40PM] F
 9:  150: [03:30PM - 04:30PM] F
10:  175: [05:40PM - 06:40PM] E
11:  275: [07:00PM - 08:00PM] G

1.) 计算项目集中的不同类型。这在 O(nlogn) 中是可能的。该示例为 7。

2.) 创建一个 n*n 矩阵，表示哪些节点可以到达实际节点，哪些可以从实际节点到达。例如，如果位置 (2,4) 设置为 1，则意味着图中存在从节点 2 到节点 4 的路径，并且 (4,2) 也设置为 1，因为可以从节点 2 到达节点 4 . 这在 O(n2) 中是可能的。例如，矩阵看起来像这样:

111111111111
110011111111
101011111111
100101111111
111010111111
111101000001
111110100111
111110010111
111110001011
111110110111
111110111111
111111111111

3.) 现在我们在每一行中都有可以到达的节点。我们还可以在尚未标记的行中标记每个节点，如果它与可以到达的节点类型相同。我们将矩阵位置设置为 0 到 2。这在 O(n3) 中是可能的。在示例中没有从节点 1 到节点 3 的路径，但是节点 4 具有与节点 3 相同的类型 D，并且存在从节点 1 到节点 4 的路径。所以我们得到这个矩阵:

111111111111
110211111111
121211111111
120121111111
111212111111
111121020001
111112122111
111112212111
111112221211
111112112111
111112111111
111111111111

4.) 仍然包含 0 的节点(在相应的行中)不能成为解决方案的一部分，我们可以从图中删除它们。如果至少有一个节点要移除，我们将在步骤 2 中重新开始。)使用较小的图。因为我们至少删除了一个节点，所以我们必须返回到第 2 步。)最多 n 次，但大多数情况下这只会发生几次。如果矩阵中没有剩余的 0，我们可以继续第 5 步。)。这在 O(n2) 中是可能的。例如，不可能用节点 1 构建一个路径，该路径也包含一个类型为 C 的节点。因此它包含一个 0 并像节点 3 和节点 5 一样被删除。在下一个循环中，较小的图节点 6 和节点8 将被删除。

5.) 计算项目/节点的剩余集合中的不同类型。如果它小于第一个计数，则没有可以表示所有类型的解决方案。所以我们必须找到另一种方法来获得一个好的解决方案。如果它与第一次计数相同，我们现在有一个较小的图，它仍然包含所有可能的解决方案。 O(nlogn)

6.) 为了得到一个解决方案，我们选择一个起始节点(哪个无关紧要，因为图中剩下的所有节点都是解决方案的一部分)。 O(1)

7.) 我们从选择的节点中删除每个无法到达的节点。在)

8.) 我们像在步骤 2.) 和 3.) 中为该图创建一个矩阵，并删除无法像步骤 4.) 中那样到达任何类型节点的节点。 O(n3)

9.) 我们从之前选择的节点中选择下一个节点之一，然后继续 7.) 直到我们到达终点节点并且图中只剩下一条路径。

这样也可以得到所有路径，但仍然可以是指数级的。毕竟它应该比在原始图中找到解决方案更快。