9

ここで興味深い質問があります。N 個の間隔 ([開始、終了]) のセットが与えられた場合、間隔ツリーを使用して重複する間隔の最大数を見つけます。

StackOverflowに関する同様の質問で O(N) 解が提供されましたが、間隔を前処理して間隔ツリーにすることができれば、おそらく対数時間で解を見つけることができます。

実際、Cormen らによる「Introduction to Algorithms」の演習問題は、これが赤黒間隔ツリーを拡張することによって可能であることを示唆しています。これを行う方法はありますか？

4

2 に答える 2

-1

いくつかの例を見てください。これにはインターバルツリーを使用できます。CGALは、このための堅牢な実装を提供します。あなたの問題に似た別の興味深い例。

于 2010-09-21T04:25:27.403 に答える
-1

拡張 AVL セルフ バランシング ツリーに基づくインターバル ツリーは、http ://code.google.com/p/intervaltree/ にあります。それを行う方法を示します。赤黒木にも同じことができます。

于 2012-07-25T00:28:15.997 に答える