問題タブ [interval-tree]

ここから C# 間隔ツリー コレクション クラス クラスを使用していますhttp://intervaltree.codeplex.com/SourceControl/list/changesets -> 右側 -> ダウンロード。

指定されたコレクションと重複するコレクションから間隔を取得する必要があります。これは で簡単に思え.Get(left, right)ます。ただし、2D 間隔が必要です。明らかに、これは 1D 間隔から始めるのは難しくありません。

ネスティングで行われていると聞いたことがあります。

ただし、これも意味がないようです。他の何よりも、間隔を移動するのはコストがかかるようであり、それらをどこに追加するかを考えるのは複雑に思えます。

どのように実行するかはわかりませんが、これを行ったかどうかはわかりませんGet(left, right, upper, lower)。おそらく、stored_type のインスタンスが存在し、両方のセットに属しますが、状況が変化したときにセットが再構成された場合、問題は発生しますか?

ただし、 a が.Get(...)返されますList<stored_type>。間隔リストにあるものよりもはるかに少なくなりますが、これにはまだ大量のアイテムListがあり、迅速に処理する必要がありますが、独立して注文する必要はありません. を LinkedList や HashSet などの別のコレクションに変換してList、単にトラバースするよりも速くトラバースできますか?

編集：

したがって、おそらく次のようなものです。

to_HashSet() がないことを除いて、2 つのセットが交差する場所を見つけるために二重ループを使用する必要があります。また、各要素の x と y はハードコードされています。

フィードバックが欲しいです。以前は、HashSet と foreach を使用してそれをステップ実行し、各要素を比較して目的の境界をオーバーラップさせていました。

長方形の領域をキャンバスに格納するための2次元の区間木が必要です。
クリックされたポイントを含む領域、または長方形の選択と重なっている領域を特定する必要があります。

この目的のための2次元区間木の標準的な実装はありますか？

boost::icl::interval_map で間隔の数を取得する組み込みの方法はありますか? 私はドキュメントでそれを見つけることができません。メソッドsize()には別の目的があるようです。

これは、インターバルツリーをトラバースするために私が書いた関数です。ただし、一部のノードにアクセスできないことに気付きました。コードがかなり明確であると仮定すると、どこで失敗したかを知りたいです。

開始/終了日時の値のリストを考えると、次の3つのことを検証する必要があります。

1. 各間隔で、開始時刻は終了時刻より前です
2. リスト要素間に重複は存在しません。各開始/終了スパンは、リスト全体の離散間隔を表す必要があります
3. シリーズにギャップはあり得ません。最初から最後まで、継続的にカバーする必要があります。

だから、与えられた：

成功の結果が示されます。

与えられた

開始日が最初の要素の終了日より後に来ることを示すメッセージが提供されます。

与えられた

最初の要素と2番目の要素の間に重複が存在することを示すメッセージが提供されます。

与えられた

2番目と3番目の要素の間にギャップが存在することを示すメッセージが提供されます。

最初の要件は単純なものです。問題は、より広範な検証にどのように組み込むのが最適かということです。

2番目の要件は、以下の記事である程度満たされていますが、1組の間隔でしか機能しないため、各要素を他のすべての要素と比較する必要があるため、O（n ^ 2）を実現します。2つの日付範囲が重複しているかどうかを判断する

この記事-間隔のリストで間隔の重複を検索しますか？-2番目の要件により適切に対処しているようで、最初の要件は区間木の母集団に組み込むことができます。

したがって、3番目の要件が残ります。区間木を使用して、区間全体のギャップを決定することは可能ですか？

これはJavascript、node.jsにあることをお伝えします。ただし、これをHaskellまたは別の関数型言語で解決するのは興味深いでしょう...

ありがとう！

r/スティーブ

次の写真を考えてみましょう

これはいわゆる範囲ツリーです。わかりませんが、二分探索木に似ているので、要素を挿入する場合は、二分探索木挿入時と同じ手順で使用できます。では、違いは何ですか？

チュートリアルを読んだことがありますが、これはkdツリーのバリエーションであり、検索ツリーのクエリ（幾何学的な点の検索など）であると思いますが、どのように構築するのですか？二分探索木のように、または追加のパラメータが必要ですか？多分このように

挿入中にチェックする必要があります

範囲ツリーの構築方法を正しく理解するのを手伝ってください。

重複する可能性のある（日付）間隔がたくさんあります。間隔はさまざまなソースから取得されます。この「タイムライン」を「平坦化」してから、間隔がなかったすべての間隔を見つけたいと思います。

http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/ の「より複雑な例」セクションを参照してください。したがって、作曲家が生きていなかった区間を見つけたいと思います。

それ、どうやったら出来るの？そして、PHPでそのようなことをどのように実装しますか? PHP には、ツリーを構築するための簡単な関数もありますか?

多くのthx！

編集 私の入力は、次のような開始日と終了日を含むいくつかの配列 (2、3、または 4) です。

同じことが myarray2、myarray3 などにも当てはまります。

モジュールを使用しようとしていSet::IntervalTreeますが、要素をループに挿入すると、同じノードポインターが得られると思います。

それらをループの外側に次々と順番に挿入すると、ノードは正常に挿入され、find/find_window呼び出しは完全に機能します。しかし、ループに追加されたノードでは、find関数は奇妙な結果をもたらします。

これが出力です。ノードポインタを確認してください。ループから追加されたものは同じポインタを持ち、間違った間隔を返します（これは同じポインタ値が原因だと思います）。

ウィキペディアでインターバルツリーについて読んでいます。deleteでメソッドを実装する方法を知っている人はいますJavaか? 削除アルゴリズムへのリンクはhttp://en.wikipedia.org/wiki/Interval_tree#Deletionです

間隔のセットが与えられた場合: {1-4, 6-7, 10-12} 新しい間隔: (9,11) を追加して、最終的な解が「マージ」されるようにします: 出力: {1-4, 6-7, 9-12}。合併は両側（低域と高域）で発生する可能性があります。

この質問が複数の場所で回答されているのを見ました。誰かが Interval Tress の使用を提案していましたが、正確にどのように使用するかについては説明していませんでした。私が知っている唯一の解決策は、間隔を開始時間の昇順に並べ、それらを繰り返し処理し、適切にマージしようとすることです。

このユースケースで間隔ツリーを使用する方法を誰かが理解するのを手伝ってくれれば、それは素晴らしいことです!

[私は CLRS の本でインターバル ツリーをたどってきましたが、それらはマージについては話していません。彼らが話しているのは、挿入と検索だけです。]