最多有2個重疊的區間選擇算法

Question

我想解決this problem，其中給出N（N < = 1000）區間，算法應該計算（大小）最大的區間子集，使得沒有三個區間該子集共享一個共同點。現在我只看到一個動態編程算法。

我的想法是通過結束時間對間隔進行排序，然後考慮以下子問題： A [i] - 僅使用第一個i間隔的問題解決方案（即最大間隔數）。

現在我的問題是關於復發：如果第i間隔被採用，那麼我無法找出復發。

有人可以解釋我做錯了什麼地方（是子問題的定義還是我錯過了重複子問題）？

---

EDIT（新的想法？） 經過一番研究，我發現這個DP solution爲一般作業選擇算法。因此，下一個想法是獲得q數組，其中q[i] =最後一個間隔的索引與第i個間隔不重疊。 然後是肯定的，該公式用於計算A [1]當第i個間隔取會是這樣（注意丟失的部分）：

A[i] = 1 + A[q[i]] + [missing-part]; 
//1 stands for the i-th interval 
//A[q[i]] stands for the solution of the intervals that do not overlap with with the i-th interval 
//[missing-part] is the maximum number of intervals from the intervals that overlap with the i-th intervals that are safe to be added. 

的問題依然存在：如何計算缺失部分？

---

EDIT（貪婪的解決方案，而不是想要的解決方案） 貪心的解決方案是非常簡單的，非常類似於Job Selection Problem，與其他檢查，添加一個新的區間時，也必須保持不存在未處理的間隔這打破了問題的狀況。

Answer 1

雖然我想不出動態規劃的解決方案，我至少可以認爲一個有效的解決方案，它的工作原理，這可能有助於反正的：

1. 查找區間的所有成對重疊。如果我們將間隔想象成數字線上的線段，那麼我們可以使用線掃描算法在O（n log n）中有效地執行此操作，該算法通過開始位置減少到排序間隔，然後對它們進行線性掃描。

2. 將問題轉化爲圖形。每個輸入間隔都是圖中的一個節點。在具有重疊的節點之間添加無向邊。或者，您可以將無向邊看作是兩個相反方向的有向邊。例如，如果間隔A和B重疊，則繪製A和B之間的無向邊，或者繪製從A到B的有向邊，並繪製從B到A的有向邊。後面的表示可能是最好的接下來的內容。

3. 使用Tarjan的算法查找圖中的所有周期。這具有複雜度O（E + V）或大致O（N）。該算法找到強連通的組件，這與循環是一樣的。只保留長度> = 3的週期，因爲這意味着3個區間共享一個公共點，這違反了我們的約束。從這裏開始，假設有K個週期。

4. 對於剩餘的週期，建立一個頻率表，列出每個節點在一個週期中出現的頻率。使用散列圖，這在所有周期的組合長度中具有O（n）複雜性。

5. 觀察到從循環中移除任何1個節點會中斷該循環。如果我們刪除M個週期中發生的節點，我們將打破M個週期。我們的目標是打破所有K個週期，並通過儘可能地移除最少的節點來完成。要做到這一點，迭代刪除最重要的節點，直到不再有周期存在。我們最終會得到一組刪除的間隔。該組的補充是一組間隔，使得沒有3個共有點。這個補充集的基數是我們的解決方案。

我相信我們可以在O做第5步（N log n）的時間，如果我們用它們的頻率，我們完成散列後的元素進行排序，然後反覆刪除最常見的元素，它打破了所有的元素所關聯的週期也會導致我們刪除這些週期中的所有節點。實際上，我們可以在線性時間內做到這一點，因爲我們的頻率是線性計數，所以我們可以使用桶或基數排序。從破碎的循環中刪除節點也是線性時間，因爲我們至多會刪除它們中的所有N個，然後再也不會再考慮它們。

上面的文字是直通式的，因爲找到要移除的所有頂點的最小集合是NP-Complete，稱爲計算反饋頂點集（http://en.wikipedia.org/wiki/Feedback_vertex_set）。已知的這個問題的確切解決方案是指數型的。