3

n個の整数値のセグメントのベクトルが与えられた場合、他のセグメントのほとんどを含むセグメントを計算するためのO（n log n）アルゴリズムを探しています。実際、私はそれらのセグメントの数にのみ興味があります。

セグメントツリーと区間ツリーのバリエーションを試しましたが、関連するものはありません。私が抱えている本当の問題は、半順序から来ています。順序が合計の場合、包含ツリーを直接計算することで問題がはるかに簡単になります。

例 ：a = [4;11] b = [2;7] c = [5;8] d = [6;7] e = [3;9] f = [1;10] g = [10;42]

ここに、ecbを含むfと最大のdがあります。もちろん、gははるかに長いですが、他のセグメントは含まれていないため、最大のセグメントの問題ではありません。

順序グラフを表示できます（推移的なアークは表示されていません）：

f -----> b  ---> d
  \-->e--->c-/
       a-/
g

私にとっての主な問題は、セグメントを処理している間は除外できないことです。これは、ある時点で、fに含まれていないサブセグメントが表示され、最大のセグメントになる可能性があるためです。

4

2 に答える 2

2

O（n log n）が可能です（私は開いた間隔を想定しており、端点が重なっていないと仮定しています）

すべてのエンドポイントを並べ替えられたリスト（昇順）に並べ替え、特定のポイントがどの間隔（たとえばIDを使用）および間隔のどの端であったかを追跡します。

ここで、以下をサポートするデータ構造を維持します。

AppendAtEnd(interval_id)
int GetPosition(interval_id)
Value Remove(interval_id)
IncrementValuesLessThanPosition(j)

これは、キー（intervals_ids）を受け取り、それらの順序付き（挿入時間による）リストを維持する構造です。追加の値は最初は0で、サブ間隔を追跡するために使用します。

最後に挿入できます。idを使用して削除し（そして対応する値を取得し）、idの位置を取得し（リンクリストを使用して実装されている場合は頭からの距離のように考えてください）、リストの特定のプレフィックスのすべての値をインクリメントします。

この構造を問題に使用するために、上記の並べ替えられたリストをたどり、区間の左端点を確認するたびに、AppendAtEndを呼び出します。

間隔の右端点を確認するたびに、その位置を取得して削除し、その位置よりも小さいすべての値をインクリメントします（基本的に、この削除された間隔をサブ間隔として持つすべての間隔）。

適切な装飾情報（サブツリーの合計やノード数など）を備えたバランスの取れたツリーを使用すると、各操作がO（log n）になるように実行できます。

于 2013-03-06T17:17:33.300 に答える
2

O（n log n）で直接解を見つけました。

最初に辞書式順序を使用してセグメントをx座標の昇順で並べ替え、次にy座標の降順で並べ替えます。セグメント（a、b）>（a'、b'）の場合、この順序が与えられると、a>a'またはa= a'のいずれかであるが、b<b'であることが保証されます。いずれにせよ、（a、b）に（a'、b'）を含めることはできません。残りのセグメントの数は、nからこのソートされた配列のセグメントkのインデックスを引いたものです。それらのセグメントをSkすることに注意しましょう。

これらのセグメントのうち、逆の順序（yを減らしてからxを増やす）を使用できます。セグメントkのインデックスは、セグメントkに含まれないSkのセグメントの数になります。

ここでの秘訣は、直接含まれるセグメントを数えるのは難しいことですが、左側（または右側）の含まれるセグメントと含まれないセグメントを数えるのは簡単です。

擬似コードで要約するには：

segments as triples (low,high,id)
orderedXY = sort segments first inc. x then dec. y then inc. id
orderedYX = sort segments first dec. y then inc. x then inc. id
return max(n - orderedXY.find(id=k) - orderedYX.find(id=k) - 1, for every id k)

このアルゴリズムは、2つの種類があるため、O（n log n）です。

編集：重複したセグメントを処理するには、3番目のキー（セグメントのID）で並べ替える必要があります。このように、ソートは安定しています。

編集'：各セグメントを1回だけカウントするには、1を引く必要があります。

于 2013-03-06T17:34:26.217 に答える