日曆調度算法

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（n ）。之後，可以使用類似depth first search的算法找到所有路徑，然後從每個路徑中刪除重複的類型。 對於該示例，有4種解決方案，但沒有一種具有所有類型，因爲示例無法執行Go to Gym,Lunch With Steve和Go to Tennis。

此外，搜索所有路徑的最壞情況複雜度爲O（2 ⁿ）。例如，下面的圖具有從開始頂點到結束頂點的可能路徑。

example graph2 http://web.archive.org/web/20120103133636/http://img295.imageshack.us/img295/2848/cal.gif

有可能會進行一些優化，比如搜索所有路徑之前併購一些頂點。但這是不可能的。在第一個例子中，即使它們是相同類型，頂點3和4也不能合併。但是在最後一個例子中，如果頂點4和5的類型相同，它們可以合併。這意味着您選擇的活動無關緊要，都是有效的。這可以顯着加速所有路徑的計算。

也許還有一種巧妙的方法可以考慮重複類型以消除它們，但最壞的情況仍然是O（2 ⁿ）如果您想要所有可能的路徑。

EDIT1：

有可能以確定是否存在包含所有類型，並得到一件T至少在多項式時間內這樣一個解決方案集。我發現一個算法的最壞情況時間爲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 * n矩陣，它表示哪些節點可以到達實際節點，哪些節點可以從實際節點到達。例如，如果位置（2,4）設置爲1，則意味着在圖中存在從節點2到節點4的路徑，並且（4,2）也被設置爲1，因爲節點4可以從節點2到達這在O中是可能的（n ）。例如，矩陣看起來像這樣：

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

3.）現在我們在每一行都有哪些節點可以到達。我們還可以將每個節點標記爲尚未標記的行，如果它與可達到的節點類型相同。我們將矩陣位置從0設置爲2.這可以在O中進行（n ）。在該示例中沒有從節點1到節點3的方式，但節點4具有相同類型的d爲節點3並且存在從節點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.）我們刪除從選定節點無法到達的每個節點。 O（n）

8.）我們創建一個像在步驟2中的矩陣）和3.），並刪除無法到達任何類型節點的節點，如步驟4）。 O（n ）

9.）我們從我們之前選擇的節點中選擇一個下一個節點，然後繼續7.），直到我們處於末端節點並且圖形只剩下一條路徑。

這樣也可以得到所有的路徑，但仍然可以指數多。畢竟它應該比在原始圖中找到解決方案更快。

Answer 2

既然你在尋找每一個可能的時間表，我認爲你會發現最好的解決方案將是一個簡單的窮舉搜索。

算法上我唯一可以說的是你的字符串列表的數據結構非常糟糕。

該實現是巨大的語言依賴，所以我甚至不認爲僞代碼會有意義，但我會嘗試給出基本算法的步驟。

1. 彈出相同類型的前n項，並將它們放入列表中。

2. 對於列表中的每個項目，將該項目添加到計劃集。

3. 彈出下列n個相同類型的清單。

4. 對於在第一個項目結束後開始的每個項目，放在列表中。 （如果沒有，則失敗）

5. 繼續直到完成。

最難的部分是確定如何構建列表/遞歸，因此它是最優雅的。

Answer 3

我會爲此使用Interval Tree。

生成數據結構後，可以迭代每個事件並執行交集查詢。如果找不到交點，它將被添加到您的時間表中。

Answer 4

是窮舉搜索可能是一個選項：

初始化部分安排與重疊產生的（如9-9.30 和9.15-9.45）

的foreach部分調度到目前爲止生成一個列表最早任務新的部分日程添加到每個局部規劃不重疊的最早的任務（產生關係的情況下，不止一個）

新的局部復發的時間表

在你的情況initlialisation將只生產(8-9 breakfast)

第一次迭代後：(8-9 brekkie, 11.40-12.40 gym)（無關係）

第二次迭代後：(8-9 brekkie, 11.40-12.40 gym, 12.40-1.20 lunch)（無關係再次）

這是一個樹搜索，但它很貪婪。它留下了跳過健身房並提前享用午餐的可能性。

Answer 5

嗯，這讓我想起了大學裏的一項任務，我會描述我能記得的東西 運行時間是O（n * logn），這很不錯。

這是一個貪婪的approuch .. 我將細化的要求升技，告訴我，如果我錯了.. 度算法應返回的非碰撞任務的MAX子集（總長度方面？或量的活動？我想總長度）

我首先爲了通過精加工時間（第一最小精加工時間，最後的最大值）= O（nlogn）

Find_set(A): 
    G<-Empty set; 
    S<-A 
    f<-0 
    while S!='Empty set' do 
    i<-index of activity with earliest finish time(**O(1)**) 
    if S(i).finish_time>=f 
     G.insert(S(i)) \\add this to result set 
     f=S(i).finish_time 
    S.removeAt(i) \\remove the activity from the original set 
    od 
    return G 

運行時間分析列表： 初始排序：nlogn 每次迭代O（1）* n = O（n）

總O（nlogn）+ O（n）〜O（nlogn）（好吧，給定O符號弱點來表示真正的小複雜性數字..但隨着規模的增長，這是一個很好的算法）

享受。

更新：

好了，好像我已經誤讀後，您也可以使用動態編程，以減少運行時間，有在7-19 link text頁的解決方案。

你需要調整算法，首先你應該建立表格，然後你可以很容易地得到所有的變化。