重複していない区間を歩くためのアルゴリズム

Question

ソートされたオーバーラップしない区間（ゼロベース、半開）のリストがあります。

{[0, 5), [10, 20), [35, 40)}

の（すなわち右10点の位置を移動させる）Iは間隔（ここで言う、3）及び+10のステップ値のいずれかのポイントがあるとしましょう。 O（1）時間で私の最終的な位置を計算できるアルゴリズムはありますか？ （EDIT：多分私が言うべきで、Oよりも良い何かが（N））の間隔でカバーされていない

番号が存在しない位置とみなされるので、上記の間隔のステップ+10との位置3は（19の最終位置につながります+1は4に移動し、残りの+9は位置10から位置19まで開始します）。もう1つの例は、位置が15、開始値が-10の場合、最終位置は0です。

最終的な位置は、常に1つの区間で終了すると仮定することもできます。しかし、どの間隔からカウントを開始すべきか分かっているかもしれません。

もちろん、O（n）時間（n =間隔の数）で間隔リストを繰り返し処理できます。しかし、私はこれを攻撃するより良い方法があるべきだと感じています。

P.S.この問題に名前がありますか？これは、それが適切な名前を持つ必要があるように感じるが、私はそれが何であるか分からない。

Answer 1

あなたは簡単に（非リーフノードはそのサブツリーの最小被覆間隔、幅の実際の合計の両方を公開する必要があります）、バイナリツリーにあなたの間隔を配置することにより、対数時間に

を得ることができます

ので、間隔のあなたの元のセットビットを変更すること、

{[0, 5), [15, 20), [25,30), [35, 40)} 

は

   {cover:[0,40), size:20} 
      /      \ 
{cover:[0,20), size:10} {cover:[25,40), size:10} 
    /   \   /   \ 
{[0,5), 5} {[15,20), 5} {[25,30), 5} {[35,40), 5} 

のようなツリーとして表現されます

ここで、カバーは、サブツリーをカバーする最小の間隔であり、サイズは、ギャップを除くインターバル幅です。

だから、あなたの3 + 10ケースを処理するために、我々はような何か：私たちは右に移動している（対数時間）

3を含む区間を見つけること

1. 通常のバイナリツリーの検索を（正のステップ）この区間はその方向に5-3=2をカバーしています。 2<10ですので、まだ完了していません。残りの距離（10-2=8）を調整し、ツリー内を右に移動してください。それは

2. この間隔は5<8をカバーし、次の右の子を見て意味して

   現在のノードは、私たちの親の左の子であるので、我々はまだ行われていません。残りの距離（8-5=3）を調整し、ツリー内を右に移動してください。それが私たちの祖父母の右の子に、この場合には、レベルを上がっていく意味して

   現在のノードは、私たちの親の右の子である

   この間隔は10>3カバーするので、私たちのエンドポイントはどこかで

3. ここに。しかし、これは葉ではないので、左の子供から始めて、再び下に行く必要があります。親/子範囲は重複しているので、このステップでは残りの距離を消費していません。

4. この区間は5>3をカバーするので、最終的に正しい葉の間隔が見つかりました。私たちのエンドポイントは、トラバーサルが右線形に見えるものの、いずれかがあった場合、我々は中間部分木の上にスキップしている可能性があること25 + 3 = 28

注意です。それはすぐにはっきりしませんが、それでも対数でなければなりません。