問題タブ [interval-intersection]

範囲の交差は単純ですが、重要な問題です。

それはすでに2回答えられています：

• 番号範囲の共通部分を検索
• 日付範囲の比較

最初の解決策はO（n）であり、2番目の解決策はデータベース用です（もちろんO（n）未満です）。

私は同じ問題を抱えていますが、nが大きい場合、データベース内にいません。

この問題は、長方形内のポイントをすばやく取得するための2Dポイントの保存と非常に似ているようですが、どのようにマッピングされるかわかりません。

では、範囲の検索のコストがO（n）未満になるように、範囲のセットをどのデータ構造に格納しますか？（Javaで利用可能なライブラリを使用するための追加のクレジット）

編集：

交差するすべての範囲のサブセットを取得したいのですが、検索範囲が複数の範囲と交差する可能性があることを意味します。

JavaでO（n）未満である必要があるメソッドは次のとおりです。

Rangeは、intの開始と終了のペアを含む単なるクラスです。

これは不可能な質問ではありません、私はすでに解決策を持っています、私はそれを行うためのより標準的/より簡単な方法があるかどうかを見たかっただけです

2 つの整数区間が重複しているかどうかをチェックするクラスを作成しました。しかし、私はこの解決策があまり好きではありません。より良い、よりシンプルな方法でそれを行うことは可能だと思います。

}

私の質問をする最良の方法は、明確な例を使用することです。2つのタイムライン（秒単位の時間など）AとBについて考えます。ここで、各タイムラインの間隔は次のとおりです。

最初のa間隔が最初のb間隔と重なっていることに注意してください。2番目のa間隔は、1番目、2番目、および3番目のb間隔と重なり、以下同様に続きます。

最終的に、以下のようにb間隔と重なるa間隔のインデックスを示す出力が必要です。

大きな課題は次のとおりです。ソリューションにfor/whileループを含めることはできません（「理由」は無関係です）。これは、ベクトル/行列/配列/並べ替えまたは他のツールを使用して効率的に実行できますか？MATLABの実装は完璧ですが、他の言語でも問題ありません。前もって感謝します！

円の角度セクタを表すラジアン単位の間隔があるとします。最初の数字は間隔の始まり、2 番目の数字は間隔の終わりです。両方の数値は、反時計回り、つまり三角関数の方向に接続されます。テスト間隔との交点を知りたいです。

最後のセクターはインターバルと重ならないため、交差はありません。視覚化のために

角度セクターの交点を見つけるための実装されたソリューションは見つかりませんでした。どんな助けでも大歓迎

この質問のより一般的なバージョンは、ここで回答されています。ユーザーは、このより具体的なバージョンの質問を別の投稿として行うことを提案しました。

次のような 2 つの論理ベクトルがあります。

連続する値の範囲 (この例では 1111) の間の交差を、最初のベクトルの 1 の実行ごとに最大 1 つの交差がカウントされるようにカウントしたいと考えています。

上記の回答を使用sum(rle(x & y)$values)すると、上記のベクトルの交差の総数を2として数えることができますが、 1と予想されます。