問題タブ [interval-tree]

時間間隔のリストが与えられた場合、重複しない最大間隔のセットを見つける必要があります。

例えば、

次の間隔がある場合：

また、時間は の範囲内にある必要があります[0000, 2400]。

重複しない間隔の最大セットは です[0600, 0830], [0900, 1130], [1230, 1400]。

最大セット梱包はNP-Completeということで了解しました。私の問題 (開始時間と終了時間のみを含む間隔) も NP-Complete であるかどうかを確認したいと思います。

もしそうなら、指数時間で最適な解を見つける方法はありますが、よりスマートな前処理とデータの刈り込みが必要です。または、固定パラメーターの扱いやすいアルゴリズムを実装するのが比較的簡単な場合。私は近似アルゴリズムに行きたくありません。

次のフィールドを持つ何百万ものドキュメントがあります:
名前 (文字列)、開始バージョン (int)、終了バージョン (int)。

クエリに答えるすべてのレコードを効率的にクエリする必要があります:
バージョン >= "開始バージョン" およびバージョン<="終了バージョン" であるすべてのドキュメントを選択します

上記のクエリの実行には 50 ～ 100 ミリ秒かかりましたが、各バージョンのタグ付けによる同様のクエリには 15 ミリ秒しかかかりませんでした。

私の質問は、Solr がそのようなクエリをどれだけ効率的に処理できるかということです。
代替ソリューションは歓迎されます。
フィールドの値/タイプは、必要に応じて変更できます。

N 個の間隔のセットが与えられた場合: 各間隔について、他のどの間隔が最大のオーバーラップを持っていますか?

例: { [0,5], [2,9], [2,3], [4,9] }:

[0,5]: [2,9] (4 の重なり)

[2,9]: [4,9] (6の重なり)

[2,3]: [0,5] または [2,9] (2 の重複)

[4,9]: [2,9] (6の重なり)

N は大きくなる可能性があるので、インターバル ツリーが必要だと思います。ただし、私が見つけた投稿や出版物には、このタイプのクエリへのアプローチが記載されていません。クエリの結果は、クエリ間隔の中心点を含む場合と含まない場合があるため、間隔ツリー ノードからの 3 つのパス (中央の左、重複する中央、中央の右) のいずれかにある可能性があります。そのため、結果を取得するための log(N) トラバーサル メソッドは考えられません。

また、[2,3] の場合は、どちらを選んでもかまいません。最大交差間隔は任意に選択できます。クエリごとに返される結果は 1 つだけです。

これらのクエリのそれぞれに log(N) で回答して、Nlog(N) の全体的なソリューションを提供できますか?

編集:私が解決した疑似コード:

間隔のリストを重複しないサブ間隔に分割しようとしています。たとえば、私の入力が

出力を

出力を、元の間隔のリストと同じユニオンを持つ間隔のリストにする必要がありますが、複数の異なるサブ間隔の重複するサブ間隔はすべて異なる間隔になります。

私の最初の考えは、すべての間隔を最初の要素でソートし、重複がある場合は新しい間隔を作成する必要があるということですが、これを機能させるのに苦労しています。これは多くの区間問題とは本質的に異なるように思われるので、どんな提案でも素晴らしいでしょう!

ここに問題があり、ここに解決策があります。

最初の部分は簡単です。どんなに頑張っても手に入らない第二部です。基本的に 2 つの間隔のセットがあり、1 つの間隔が別の間隔内に完全に収まっていない交差点をすべて見つける必要があります。

目が充血するまで問題設定コードを見つめていました。まだこのビットを理解できません:

それはどのように機能しますか？アルゴリズムは何ですか？

社説には、インターバルツリーまたは「バイナリインデックスツリー」を使用してこれを解決できることが記載されています。間隔ツリーとは何か、またどのように役立つかについては、多かれ少なかれ理解しています。しかし、プロブレム セッターは明らかにそれを使用しておらず、「バイナリ インデックス ツリー」は検索に表示されません。関連性があることは確かですが、その方法がわかりません）。

何か助けはありますか？読む必要のある文献へのポインタはありますか?

重複する間隔のセットがあります。それぞれの間隔から 1 つの要素を選択して、それらがグループ化されたときに選択範囲に最小のギャップが生じるようにする必要があります。

グループ化とは、連続する要素がグループ化されることを意味します。また、要素に対して他の間隔から連続する要素がない場合、これは 1 つの要素を持つグループと見なされます。

つまり、ギャップを最小限に抑えることで、そのようなグループの数を減らし、より大きなグループを形成しようとしています

インターバルツリーについて見て、それが役立つかもしれないと考えましたが、それを自分の利益のためにどのように使用するかわかりません

問題を解決するためにどのようなアプローチをとればよいか教えてください。

例：

間隔 (境界を含む)

考えられる解決策

上記の要素を選択して形成されるグループ

したがって、ギャップは 4 ～ 9 の 1 つだけです。

解決する間隔ツリーについて質問があり、基本的にアルゴリズムは知っていますが、関数がメインに値を返すときにコードに問題があります。

私が抱えている問題は、特定のインデックス間の最大値を見つけて、配列内の値を更新することです。したがって、n 個の数値と m 個の演算を含む初期配列があります。操作が 0 で始まる場合は、 index 間の最大値を調べる必要がありますx。操作が 1 で始まる場合、x初期ベクトルのインデックスの値を で更新する必要がありますy。

問題は、質問によっては正しい答えをファイルから取得することもあれば、単に「乱数」を与えることもあります。

答えを監視できるようにコード中にいくつかのprintfを実行しましたが、最後に関数で値を返す前に完全に正しいことがわかり、関数の直後にメインでチェックすると結果が得られます先ほども言いました。

これは私がテストしている入力です:

コード：

長い投稿と長いコードで申し訳ありません。何かを省略した場合は、思い出してください。

前もって感謝します！