日历调度算法 [英] calendar scheduler algorithm
问题描述
我在寻找一种算法，给定一组包含的开始时间的项目，结束时间，类型和身份证，这将返回一组项目的所有集合适合（不重叠的时间及各类在一起重新psented在集合$ P $）。
I'm looking for an algorithm that, given a set of items containing a start time, end time, type, and id, it will return a set of all sets of items that fit together (no overlapping times and all types are represented in the set).
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)]]
谢谢！
推荐答案
这可以使用图论解决。我想创建一个数组，其中包含的项目排序的开始时间和结束时间等于开始时间：（增加了一些项目的例子）：
This can be solved using graph theory. I would create an array, which contains the items sorted by start time and end time for equal start times: (added some more items to the example):
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加入：
After that i would create a list with the array no. of the least item that could be the possible next item. If there isn't a next item, -1 is added:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
1 | 7 | 4 | 5 | 6 | 6 | 7 | -1
使用该列表，可以产生一个向无环图的。每个顶点具有从下一个项开始的顶点的连接。但对于顶点的地方已经是一个顶点bewteen他们没有边缘而成。我会尝试用例子来解释。为顶点0的下一个项目是1.因此，一个边缘是由0 - > 1.从1的下一项是7，这意味着对它们是从顶点0连接的顶点的范围现在是从 1（7-1）。因为顶点2是在1至6的范围内，另一个边缘0 - > 2由和范围更新 1至（4-1）（因为4是2下一个项目）。因为顶点3是在1至3多一个边缘0的范围内 - > 3制成。这是最后边沿顶点0。也就是说，必须继续与所有的顶点，导致这样的图：
With that list it is possible to generate a directed acyclic graph. Every vertice has a connection to the vertices starting from the next item. But for vertices where already is a vertices bewteen them no edge is made. I'll try to explain with the example. For the vertice 0 the next item is 1. So a edge is made 0 -> 1. The next item from 1 is 7, that means the range for the vertices which are connected from vertice 0 is now from 1 to (7-1). Because vertice 2 is in the range of 1 to 6, another edge 0 -> 2 is made and the range updates to 1 to (4-1) (because 4 is the next item of 2). Because vertice 3 is in the range of 1 to 3 one more edge 0 -> 3 is made. That was the last edge for vertice 0. That has to be continued with all vertices leading to such a graph:
到现在为止，我们都在为O（n 2 ）。之后，所有的路径可以使用深度优先搜索般的算法，然后消除重复类型的每个路径中。
对于这个例子中有4个解决方案，但没有人拥有所有类型，因为它是不可能的例子做进入健身房，午餐史蒂夫和进入网球。
Until now we are in O(n2). After that all paths can be found using a depth first search-like algorithm and then eliminating the duplicated types from each path.
For that example there are 4 solutions, but none of them has all types because it is not possible for the example to do Go to Gym, Lunch With Steve and Go to Tennis.
另外这款搜索所有路径有邻最坏情况的复杂性（2 N ）。例如，下面的图有2 N / 2 从一开始可能的路径顶点结束顶点。
Also this search for all paths has a worst case complexity of O(2n). For example the following graph has 2n/2 possible paths from a start vertice to an end vertice.
有可能会进行一些优化，比如搜索所有的路径前并购一些顶点。但是，这并不是以往任何时候都可能的。在第一个例子顶点3和4，即使它们是相同类型的不能合并。但在最后一个例子顶点4和5能如果它们是相同类型的合并。这意味着它不会不管你选择哪一个活动，都是有效的。这样可以加快急剧所有路径的计算。
There could be made some more optimisation, like merging some vertices before searching for all paths. But that is not ever possible. In the first example vertice 3 and 4 can't be merged even though they are of the same type. But in the last example vertice 4 and 5 can be merged if they are of the same type. Which means it doesn't matter which activity you choose, both are valid. This can speed up calculation of all paths dramatically.
或许也有一个聪明的方法来考虑重复类型的早期，以消除他们，但最坏的情况仍然是O（2 N ）如果你希望所有可能的路径。
Maybe there is also a clever way to consider duplicate types earlier to eliminate them, but worst case is still O(2n) if you want all possible paths.
EDIT1：
有可能确定是否有包含所有类型的，并获得在多项式时间中的至少一个这样的解决方案集。我发现了一个算法为O的最坏情况下的时间（n 4 ）和O（N 2 ）的空间。我会采取一个新的例子与所有类型的解决方案，但是比较复杂。
It is possible to determine if there are sets that contain all types and get a t least one such solution in polynomial time. I found a algorithm with a worst case time of O(n4) and O(n2) space. I'll take an new example which has a solution with all types, but is more complex.
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的例子。
1.) Count the different types in the item set. This is possible in O(nlogn). It is 7 for that example.
2）创建*正矩阵，即重新presents哪些节点可达到的实际节点并且可以从实际的节点到达。例如，如果位置（2,4）被设置为1，意味着有从节点2的路径节点4在图形中和（4,2）被设置为1也是如此，因为节点4可以从节点2到达这是可能的为O（n 2 ）。对于例如矩阵会是什么样子的：
2.) Create a n*n-matrix, that represents which nodes can reach the actual node and which can be reached from the actual node. For example if position (2,4) is set to 1, means that there is a path from node 2 to node 4 in the graph and (4,2) is set to 1 too, because node 4 can be reached from node 2. This is possible in O(n2). For the example the matrix would look like that:
111111111111
110011111111
101011111111
100101111111
111010111111
111101000001
111110100111
111110010111
111110001011
111110110111
111110111111
111111111111
3。）现在我们有每一行，哪些节点可以达到。我们还可以标记在一排它尚未标记每个节点，如果是相同的类型，可以达到一个节点。我们设置的矩阵位置从0到2。这是可能的为O（n 3 ）。在该示例中没有从节点1到节点3的方式，但节点4具有相同的D型为节点3和存在从节点1到节点4的路径因此，我们得到这样的矩阵：
3.) Now we have in every row, which nodes can be reached. We can also mark each node in a row which is not yet marked, if it is of the same type as a node that can be reached. We set that matrix positions from 0 to 2. This is possible in O(n3). In the example there is no way from node 1 to node 3, but node 4 has the same type D as node 3 and there is a path from node 1 to node 4. So we get this matrix:
111111111111
110211111111
121211111111
120121111111
111212111111
111121020001
111112122111
111112212111
111112221211
111112112111
111112111111
111111111111
4）仍包含0（在相应的行）不能成为解决方案的一部分，我们可以从图中移除它们的节点。如果有至少一个节点以除去我们在第2步）与较小的图表重新开始。因为我们去掉至少有一个节点，我们必须回到步骤2）至多N次，但多数情况下，这只会happend几次。如果没有0的左矩阵中，我们可以继续执行步骤5）。这可能是在为O（n 2 ）。对于这个示例，不可能建立与节点1的路径还包含与C型的一个节点。因此它包含了一个0，并像节点3和节点5在接下来的循环与较小的图形节点6和节点除去8将被去除。
4.) The nodes that still contains 0's (in the corresponding rows) can't be part of the solution and we can remove them from the graph. If there were at least one node to remove we start again in step 2.) with the smaller graph. Because we removed at least one node, we have to go back to step 2.) at most n times, but most often this will only happend few times. If there are no 0's left in the matrix we can continue with step 5.). This is possible in O(n2). For the example it is not possible to build a path with node 1 that also contains a node with type C. Therefore it contains a 0 and is removed like node 3 and node 5. In the next loop with the smaller graph node 6 and node 8 will be removed.
5）计数的不同类型的remainig设置的项目/节点。如果它小于所述第一计数值小，没有解决方案，可重新present所有类型。因此，我们必须找到另一种方式来获得的好的解决方案。如果是相同的第一计数，我们现在有一个较小的曲线图仍持有的所有可能的解决方案。 O（nlogn）
5.) Count the different types in the remainig set of items/nodes. If it is smaller than the first count there is no solution that can represent all types. So we have to find another way to get a good solution. If it is the same as the first count we now have a smaller graph which still holds all the possible solutions. O(nlogn)
6）。为了得到一个解决方案，我们选择一个起始节点（这并不重要，因为留在图表中的所有节点都是一个解决方案的一部分）。 O（1）
6.) To get one solution we pick a start node (it doesn't matter which, because all nodes that are left in the graph are part of a solution). O(1)
7）。我们删除不能从已选定的节点到达每个节点。为O（n）
7.) We remove every node that can't be reached from the choosen node. O(n)
8）。我们创建矩阵像在步骤2）和3），选择那些图表，并删除无法到达任何类型的节点像在步骤4中的节点）。为O（n 3 ）
8.) We create a matrix like in step 2.) and 3.) for that graph and remove the nodes that can not reach nodes of any type like in step 4.). O(n3)
9）。我们选择我们之前choosen并继续7），直到我们正处在一个终端节点和图形只留下一条路径，节点的下一个节点。
9.) We choose one of the next nodes from the node we choosen before and continue with 7.) until there we are at a end node and the graph only has one path left.
这种方式，也可以得到所有的路径，但仍然可以是指数许多。毕竟它应该比原图找到解决得更快。
That way it is also possible to get all paths, but that can still be exponential many. After all it should be faster than finding solutions in the original graph.
这篇关于日历调度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
