問題タブ [interval-tree]

間隔の 2 つのリストと が与えられAますB。

ではA、区間は開始点でソートされています。A重複する区間はありません。

同様に、Bでは、区間は開始点でソートされています。B重複する区間はありません。

2 つのリスト間で重複する区間を返します。

例：

戻る：

私はインタビューでこれを得て、困惑しました。

2 つのリストの間隔を比較することを考えました。2 つの間に重複がある場合は、重複を結果リストに追加します。次に、開始間隔が短いリストのポインターを進めましたが、インタビューの終わりまでに有効なソリューションに到達できませんでした。

この問題を解決する最善の方法は何ですか?

私が現在学習しているインターバル ツリーには、ノードごとに次のデータ構造があります。

• key: すべての間隔の終点の中央値
• left, right: 左右のサブツリーを指す
• intervals: を含む間隔を含む間隔のリストkey。

より正確な情報は、このリンクにあります。

インターバル ツリーを使用したクエリの時間計算量は O(logn + k) であることがわかりました。ここで、n はインターバルの数、k は報告された結果の数です。

の部分がよくわかりませんlogn。がインターバルvツリーの現在のノードで、Qがクエリ間隔であるとします。アルゴリズムは次のようになります。

最初は、if2 つのサブツリーに入る必要があるようです。最悪の場合、すべてのツリー ノードをトラバースしなければならず、時間計算量が O(n + k) になるのではないでしょうか?