日历调度算法

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

这可以使用图论来解决.我将创建一个数组,其中包含按开始时间和结束时间排序的项目,以获得相同的开始时间:(在示例中添加了更多项目):

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

使用该列表,可以生成有向无环图.每个顶点都与从下一个项目开始的顶点连接.但对于已经是顶点的顶点,它们没有边缘.我将尝试用这个例子来解释.对于顶点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.这是vertice 0的最后一个边缘.必须继续使用导致这样一个图形的所有顶点:

到现在为止我们都在O(n ²).之后,可以使用深度优先搜索算法找到所有路径,然后从每个路径中消除重复的类型.对于该示例,有4个解决方案,但它们都没有所有类型,因为示例不可能这样做Go to Gym,Lunch With Steve并且Go to Tennis.

此搜索所有路径的最坏情况复杂度为O(2 ⁿ).例如,下图具有从起始顶点到结束顶点的2 ^n/2个可能路径.

示例图2 http://web.archive.org/web/20120103133636/http://img295.imageshack.us/img295/2848/cal.gif

可以进行更多优化,例如在搜索所有路径之前合并一些顶点.但这是不可能的.在第一个示例中,顶点3和4即使它们是相同类型也不能合并.但是在最后一个例子中,如果它们是相同类型,则可以合并顶点4和5.这意味着您选择哪个活动无关紧要,两者都有效.这可以显着加快所有路径的计算.

也许还有一种聪明的方法可以提前考虑重复类型来消除它们,但是如果你想要所有可能的路径,最坏的情况仍然是O(2 ⁿ).

EDIT1:

可以确定是否存在包含所有类型的集合并且在多项式时间内获得至少一个这样的解.我发现了一种最坏情况下为O(n ⁴)和O(n ²)空间的算法.我将采用一个新的例子,它有一个所有类型的解决方案,但更复杂.

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矩阵,表示哪些节点可以到达实际节点,哪些节点可以从实际节点到达.例如,如果位置(2,4)设置为1,则意味着图中存在从节点2到节点4的路径,并且(4,2)也设置为1,因为可以从节点2到达节点4这在O(n ²)中是可能的.对于示例,矩阵看起来像:

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

3.)现在我们在每一行都有可以到达的节点.我们还可以将每个节点标记为尚未标记的行,如果它与可以到达的节点的类型相同.我们将矩阵位置设置为0到2.这在O(n ³)中是可能的.在该示例中,从节点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(n ²)中是可能的.对于该示例,不可能构建具有节点1的路径,该节点还包含具有类型C的节点.因此,它包含0并且被移除,如节点3和节点5.在具有较小的图节点6和节点的下一循环中8将被删除.

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

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

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

8.)我们为该图创建一个矩阵,如步骤2.)和3.),并删除无法到达任何类型节点的节点,如步骤4).O(n ³)

9.)我们从之前选择的节点中选择下一个节点之一并继续执行7.)直到我们处于结束节点并且图形只剩下一个路径.

这样也可以获得所有路径,但这仍然是指数很多.毕竟它应该比在原始图中找到解决方案更快.