最大加重セグメントカバレッジアルゴリズム

Question

これは私が思ったアルゴリズム的な質問ですが、簡単な解決策は考えられませんでした。

問題は、二つの有名な問題マージ触発さ：最小セグメントカバレッジ&ナップザック問題を、そして以下のように説明する：すべてl_i, r_i in [1,M]nセグメント[l_i, r_i]を考える

。 n, Mが知られている。

各セグメントの値はv_iです。オーバーラップしていないセグメントをいくつでも選択できる場合、最大合計値はいくらですか？私は私の考えは オーバー複雑ですが、今、私の頭の中で解決策は、我々はナップザックを解決するように、動的プログラミングを使用している強い気持ちを持って

---

（感動はokです）。

1. 昇順にソート
2. でr_iによってセグメントがDP(i) := maximum value we can get using segment [0,i]を定義し、ここでインデックスはj is the largest index where r_j <= l_i, which can be found using binary search

が、私はこのソリューションはO(N lg N)のだと思います

DP(i) = max(DP(j) + v[i], DP(i-1))ステップ1の後にソートされた指標です。今、私の問題は：

1. この解決策は正しいですか？
2. より簡単で優れたパフォーマンスのソリューションはありますか？

Answer 1

セグメントカバレッジは、interval graphと呼ばれるグラフで表すことができます。 2つの重なり合ったセグメントを取ることを望まないので、あなたは区間グラフの中で最大重み付き独立集合を見いだそうとしている。この問題は一般的なグラフではNP困難ですが、幸いにも間隔グラフで簡単に解決できます。 GraphClasses websiteを見ると、線グラフの場合は、弦グラフ（区間グラフよりも大きなクラス）でも問題が解けることが分かります。また、証明するoriginal paperへの参照があります。