algorithm - 別の間隔を含む間隔の数を数えますか?

Question

それぞれが N 区間 (数直線のサブセット) を含む 2 つのリストが与えられ、各区間は始点と終点の形式を持ちます。あるリストからのこれらの間隔の何組が、別のリストからの間隔を含んでいますか?

例えば：

リストAが{(1,7), (2,9)}あり、リストBが{(3,6), (5,8)}

次に、A が B の間隔を含む間隔を持つペアの数は 3 ペアになります。

(1,7),(3,6)
(2,9)(3,6)
(2,9)(5,8)

目標は、O(n log n) を撃つことです。

現在、私のアルゴリズムは、最初に x 座標で並べ替え、それを 1 つのリストとして取得することです。次に、リストを y 座標で並べ替え、2 つのリスト間の反転を数えます。しかし、私の質問は、なぜこれが機能するのですか? 任意の洞察をいただければ幸いです。

私が現在視覚化している方法は、次の幾何学的な方法です(線の各交点は数値反転のカウントです):

注：リストのリストで反転をチェックする方法がわかりません。O（n log n）を与えるアプローチを取得しようとしています。提案を聞いて喜んで他のアプローチがある場合。

Answer 1

ツリー/グリッド アプローチも試す場合は、これがどのように機能するかを説明します。タスクには 2D は必要ありませんが、1 次元の間隔マップまたはグリッドさえ必要です。より明確なので、グリッドを選択しましょう。

ペアが 1 から 100 までの整数であるとします。その場合、サイズ 100 の配列を 1 つ持つ余裕があります。配列の各セルには空のセット (順序付きリスト) が含まれます。下の図を参照してください。

ここで、グリッドに間隔を追加し始めます。2,9 の間のすべてのグリッド セルの 1,7 と 2 の間のすべてのグリッド セルに 1 を追加します (1,2 は ID であり、挿入された間隔ごとに 1 ずつ増加します。この方法での挿入は非効率的ですが、これは修正できます)。

では、B からの間隔を確認するにはどうすればよいでしょうか。最初のセルから各 ID を取得し、それが 2 番目のセルにもあるかどうかを確認します。セルが設定されているため、チェックには O(log n) かかります。最悪の場合、B からの 1 つの間隔が A 内にある重複間隔カウントを確認するには、n O(log n) 操作が必要です。

これは、グリッドの代わりに間隔マップを使用するように拡張できます (数値が小さい整数でない場合)。また、A の間隔の数が固定されていて、メモリ要件がない場合、たとえばセットを配列に置き換えると、O(logN) は O(1) になる可能性があります。