algorithm - 指定された数値を含むすべての区間を検索します

Question

重複している可能性のある間隔のリストがあります。そして、私は値を持っています。問題は、その値を含むすべての間隔を見つけることです。値自体は包括的です。レンジ ツリー、KD ツリーなどを含むいくつかのアプローチを見てきました。

1. 間隔のリストは長いです。(50K 以上になる可能性があります)。
2. 間隔が重なっている可能性があります。
3. クエリを開始すると、間隔のリストは変更されません。
4. 一度形成されたリストは、さまざまな値で何度も照会されます。

誰かがこれを解決するためのいくつかのアプローチを提案できますか? 前もって感謝します。

Answer 1

これは明確に定義された問題で、インターバル ツリーを使用して最も効率的に解決できます (ウィキペディアのこちらとこちらを参照)。

オーバーラップが多い構成では、エントリごとに O(n) 個のセグメントを格納することになり、合計 O(n^2) 個のストレージが必要になる可能性があるため、ハッシュ テーブルはお勧めしません。

Answer 2

高価な初期化時間を気にしない場合は、言及した手法のいずれかを使用して、クエリ フェーズで遭遇する可能性のあるすべての関連値の間隔を事前に計算し、最小値と最大値に制限することができます。

これらの結果を使用してハッシュ テーブルを作成すると、O(1) で指定された値のすべての間隔を見つけることができます。