algorithm - 区間選択アルゴリズム

Question

一連の間隔があるとしましょう [s1,e1],[s2,e2]...[sn,en]

重複しない間隔のサブセットを見つけたいのですが、最大の集計時間があります。

実際、私は貪欲な解決策を探しています。それは存在しますか？

Answer 1

「貪欲」は正式な用語ではありませんが、この質問の目的のために、貪欲アルゴリズムのクラスを、区間にアプリオリな全順序を課し (つまり、入力とは無関係に)、部分解を繰り返し拡張するものと定義しましょう。利用可能な最大間隔によって。入力を考慮する

[0,2],[1,4],[3,5]
[0,2],[1,4]
[1,4],[3,5].

[0,2]、[1,4]、[3,5] の最大間隔には 3 つの可能性があります。[0,2] または [3,5] が最大の場合、欲張りアルゴリズムは 2 番目または 3 番目の入力に対してそれぞれ間違った答えを出します。[1,4] が最大値の場合、貪欲アルゴリズムは最初の入力に対して正しく答えません。