運行此次會議所需的最少天數是多少？

我是一名IT人員/數學怪人，幫助組織會議。會議期間的事件（但不是日子）已成定局。例如，我們知道某個事件將在某天發生在下午1點到3點之間。我正在嘗試編寫一個腳本，該腳本確定了我們可以運行會議的最少天數，並且沒有重疊事件。運行此次會議所需的最少天數是多少？

所有事件在一天內發生;沒有任何事件的時間跨越12am或跨越數天。

我在這個問題上的第一槍涉及到將其建模爲無向圖。我們可以讓事件表示爲頂點，並且兩個頂點之間的邊標記兩個事件重疊。然後，將問題簡化爲查找圖形的最小色數 - 在確保每個邊的端點顏色不同的同時，爲頂點着色所需的最少數量的顏色。

但是，我無法開發出一種高效的動態規劃算法，該算法在多項式時間內運行以計算色數。

還有其他線索嗎？這似乎是一個NP完全問題，但我敢打賭我們可以在多項式時間內用巧妙的時空平衡來解決問題，即動態規劃。

來源

2014-03-01 dangerChihuahua007

這的確是一個NP完全問題（見http://en.wikipedia.org/wiki/Graph_coloring）。您可以嘗試使用近似算法，或查找其他表示/解決方案。這聽起來和我上大學的AI項目很相似。您是否考慮過使用具有良好啓發式功能的A *搜索？ –

@Filipe：不，區間圖的着色不是NP-hard。事實上它很容易解決。 –

@NiklasB。嗯，很高興知道！永遠學習。謝謝（你的）信息。 –

由於您的圖是interval graph，那麼對於使用掃描線算法的一般圖而言，該問題更容易解決。假設您的事件表示爲元組(s_i, f_i)，其中s_i是事件的開始時間，f_i是結束時間（均以小時爲單位）。

然後可以使用下面的算法：

events := union of {(f_i, -1), (s_i, 1)} for all i 
sort events lexicographically 
answer := 0 
count := 0 
for (time, c) in events: 
    count += c 
    answer := max(answer, count) 

return answer

時間複雜度：O(n log n)甚至O(n)如果我們假設可能的次有限數量的（這很可能是在實踐中的情況下）。

來源

2014-03-01 23:13:24

按字典順序對事件進行排序是什麼意思？ – dangerChihuahua007

@DavidFaux：['（a，b）< (c,d) :<=> a

哇，這太棒了！謝謝。這對我們的活動有效。儘管如此，我仍然盯着這個試圖理解它背後的直覺。哈哈爲什麼-1爲結束時間？ – dangerChihuahua007

它不是NP問題，在圖形方面 - 它是critical path，但我沒有看到的事件彼此相關的（沒有定義，即事件的順序）任何提及，要解決這個

創建具有24小時0-23]（0初始化）
通過所有事件運行，並加1以各佔小時陣列（從下午1點到下午3點的事件 - 添加到第13和14只）
查找數組中的最大數 - 這會給你多少事件實際上是按時間重疊的，所以這是會議的最小持續時間（max可以在dur荷蘭國際集團第2階段）

因此，實際上它是O（N）的問題

來源

2014-03-01 23:16:41

運行此次會議所需的最少天數是多少？

回答

相關問題