間隔 (x,y) がたくさんあるので、それらをグループ化したいと思います。規則では、間隔のセットは、それらがすべて入れ子になっている最大の間隔を除いて、グループの 1 つのメンバーにすべて入れ子になっている場合、同じグループに属します。たとえば、(1,7)、(2、 4),(2,9), (8,9) は、(1,7),(2,4) と (2,9),(8,9) の 2 つのグループに分割できます。もちろん、これは一意ではありませんが、グループを減らすことができないという意味では最小限です。
さらに複雑にするために、データが大きすぎるため、すべてのデータを一度に読み込む余裕がありません。
たとえば、各ペアの最初の要素でデータをオフラインで並べ替えることができます。
この問題に適したアルゴリズムは何ですか?
非減少 x で間隔を並べ替え、非増加 y で同点を解消します。間隔を順番にスキャンします。さらに間隔が存在する場合は、最初に残っている間隔を新しいグループの囲み間隔にし、可能であれば、連続する間隔をそれぞれグループに追加します。
x <= x' <= y' <= y となる 2 つの区間 [x, y] と [x', y'] が存在するとします。次に、[x', y'] がグループを囲む間隔ではないこと、したがってグループ化が最小であることを示すことができます。[x, y] = [x', y'] の場合、[x, y] と [x', y'] が同じグループに割り当てられていることは明らかです。それ以外の場合、間隔 [x, y] は [x', y'] の前に並べ替えられます。[x'', y'] がスキャンされるときに有効な囲み区間 [x'', y''] は、x'' <= x' (ソート順による) および y' <= y <= y'' を満たす(アクティブな囲み間隔の y 座標は時間の経過とともに減少しないため)。したがって、[x', y'] はグループを開始しません。
これはどう：
範囲の開始 (最初の要素) で間隔を並べ替えます。
ソートされたセットから最初の間隔を取ります。記憶に留めておいてください。リストに追加します。
while (次のものを取る)
a. it can be fully inclusive in any of the elements in the list, add it to the group of contained interval.
b. Partial inclusive, add a new member in memory. append it to the list.
c. totally Exclusive, add it to the list, remove previous elements in the list and persist in disk.
入力グループを xy のサイズが大きい順に並べ替えます (オフライン)。
グループのリストを調べて、すべてのグループについて、その前のグループのいずれかに含まれているかどうかを確認します。もしそうなら - リストから削除し、ファイルにマークします (ファイルの説明はすぐに) そうでない場合 - それはグループです
ファイル: 入力リスト内のグループのインデックスに従って名前が付けられたファイルの構造を保持します。必要に応じてファイルを作成し、任意のファイルにすべての (x,y) ペアを保持します。
これで比較的良い答えが得られますが、それが最適かどうかはわかりません。
時間:
単純化されているかもしれませんが、与えられた仮定に基づいて適切なはずです。入力データが無限の未知のストリーム/キューであると想定しています
ここで追加の制限を適用できます (最大グループサイズなど)。