最大加權片段覆蓋算法

Question

這是一個算法問題，我認爲這是一個算法問題，但我自己想不到一個簡單的解決方案。

問題是由合併兩個著名問題的啓發：最小段覆蓋&揹包問題，並作爲中的描述：

鑑於n段[l_i, r_i]，所有l_i, r_i in [1,M]。 n, M是已知的。

每個區段的值爲v_i，如果您可以選擇任意數量的非重疊區段，您可以獲得的最大總值是多少？ （接觸是確定）

---

我有一個強烈的感覺，我的想法是 過於複雜，但現在在我的腦海中的解決方案是使用動態編程就像我們解決揹包。

1. 升序排序
2. 段由r_i定義DP(i) := maximum value we can get using segment [0,i]，這裏的索引是步驟1
3. DP(i) = max(DP(j) + v[i], DP(i-1))其中j is the largest index where r_j <= l_i, which can be found using binary search

我認爲該解決方案是O(N lg N)後的排序索引。現在我的問題是：

1. 此解決方案是否正確？
2. 有沒有更簡單，更好的性能解決方案？

Answer 1

段覆蓋率可以用一個叫做interval graph的圖來表示。由於您不想採用兩個重疊的分段，因此您正在尋找在區間圖中找到最大加權獨立集。這個問題在普通圖上是NP-hard，但幸運的是，它可以很容易地在間隔圖上求解。如果你看GraphClasses website，你可以看到問題在線性時間內是可以解決的，即使對於和絃圖（這是一個比間隔圖更大的類），你可以參考證明它的original paper。