フォームの間隔のリストがあります。間隔ごとに、その中にネストされている他の間隔の数をカウントします。 [ai, bi]
たとえば、2つの間隔がある場合、A = [1,4]およびB = [2,3]。その場合、のカウントは、 ;のネストされた間隔がないためになりBます。のカウントは、内に収まるようになります。0BA1BA
私の質問は、この問題のサブ アルゴリズムは存在しますか？間隔の数はどこにありますか？O(n2)n
編集： 間隔が満たす条件は次のとおりです。区間の終点は浮動小数点数です。a i 's / b i 'sの下限は0で、上限は最大フロートが何であれです。また、 a i <b iであるという条件があるため、長さ0の間隔はありません。
はい、可能です。
典型的な計算幾何学の「スキャンライン」トリックを借ります。
まず、より簡単な（しかし密接に関連した）質問に答えましょう。各間隔に含まれる他の間隔の数を報告する代わりに、各間隔に含まれる間隔の数を報告しましょう。したがって、間隔が2つしかない例では、intervalI0 = [1,4]は0の間隔に含まれているため値がゼロであり、I1 = [2,3]値が1の場合は1つの間隔に含まれているためです。
（a）この質問が簡単である理由と、（b）元の質問の回答にどのようにつながるかがすぐにわかります。
この簡単な質問を解決するには：すべての開始点と終了点（すべてのaiとbi ）を取得し、それらをマスターリストに入れます。このリストの各要素を「イベント」と呼びます。したがって、イベントは「間隔I37が開始した」または「間隔I23が終了した」のようになります。
このイベントのリストを並べ替えて、順番に処理します。
イベントのリストを処理するときは、「アクティブな間隔」のセットSを維持します。開始イベントは発生したが終了イベントは発生しなかった場合、間隔は「アクティブ」です。つまり、その間隔内にいる場合です。
これで、終了イベントb jが表示されるたびに、I j（= [a j、b j ]）を含む間隔の数を計算する準備が整いました。私たちがする必要があるのは、アクティブな間隔のセットSを調べて、jの前に開始した間隔の数を決定することです。これが、区間Ijを含む区間の数に対する私たちの答えです。
これを効率的に行うには、S自体を開始点でソートしたままにします。たとえば、自己平衡二分木を使用します。
イベントのリストの並べ替えは、O（2n log 2n）= O（n log n）です。自己平衡二分木に要素を追加または削除するのはO（log n）です。「平衡二分木の要素の数がx未満ですか？」と尋ねます。O（log n）でもあります。したがって、このアルゴリズム全体はO（n log n）です。
だから、それは簡単な質問を解決します。それを「簡単なアルゴリズム」と呼んでください。さて、あなたが実際に尋ねたことについて。
数直線を無限大まで延長し、-無限大まで折り返すものと考え、b i < a iで間隔を定義して、a iで開始し、無限大まで延長し、マイナス無限大まで折り返し、biで終了します。
任意の区間Ij = [a j、b j ]に対して、Complement（I j）を区間[b j、aj ]として定義します。（たとえば、区間[2、3]は2で始まり、3で終わるため、Complement（[2,3]）= [3,2]は3で始まり、無限に伸び、-無限に折り返され、で終わります。 2.）
Complement（J）にComplement（I）が含まれている場合に限り、区間Iに区間Jが含まれていることを確認してください。（これを証明してください。）
したがって、すべての区間の補集合のセットで「簡単なアルゴリズム」を実行するだけで、元の質問に答えることができます。つまり、すべての間隔を含む「アクティブな間隔」のセットSを使用して-無限大でスキャンを開始します（すべての補数に無限大/-無限大が含まれるため）。Sを終点（つまり、補数の始点）でソートしたままにします。
すべての開始点と終了点を並べ替えて、順番に処理します。区間Ij（= [a j、b j ]）の開始点に遭遇すると、実際にはその補数の終了点に到達しています...したがって、SからI jを削除し、Sにクエリを実行してその端点の数を確認します。 （つまり、開始点を補完する）b jの前に来て、それをIjの答えとして報告します。後でIjの終点に遭遇した場合、その補集合の始点に遭遇しているので、それをアクティブな区間のセットSに戻す必要があります。
この最終的なアルゴリズムは、「簡単なアルゴリズム」と同じ理由でO（n log n）です。
[アップデート]
1つの説明、1つの修正、1つのコメント...
明確化：もちろん、「自己平衡二分木」は、各サブツリーが含まれる要素の数を認識できるように拡張する必要があります。そうでなければ、「x未満の要素はいくつありますか？」と答えることはできません。この拡張は維持するのが簡単ですが、すべての実装が提供するものではありません。たとえば、私の知る限り、C++std::setはそうではありません。
訂正：アクティブな間隔のセットSに要素を追加し直したくない。実際、そうすることは間違った答えをもたらす可能性があります。たとえば、間隔が[1,2]と[3,4]だけの場合、1を押して（そしてセットから[1,2]を削除して）、次に2を押して（そして再び追加して）、次に3を押します。 ...そして2<4なので、[3,4]には[1,2]が含まれていると結論付けることができます。どちらが間違っています。
概念的には、補完間隔のすべての「開始イベント」をすでに処理しています。そのため、Sはその中のすべての間隔を開始します。したがって、心配する必要があるのは終点だけです。Sに要素を追加したくはありません。
言い換えると、間隔を折り返す代わりに、[b i、a i ]（ここでb i > a i ）は、折り返しのない[b i --infinity、ai ]を意味すると考えることができます。ロジックは引き続き機能しますが、処理はより明確です。最初にすべての「何でも-無限大」の用語（つまりエンドポイント）を処理し、次に他の用語（つまり開始ポイント）を処理します。
この修正により、私のソリューションが実際に機能すると確信しています。この定式化は、1つの入力に通常の間隔と「後方」の間隔の両方がある場合にも拡張されます（私は思います）。
コメント：この問題は注意が必要です。すべての間隔に含まれるすべての間隔のセットを列挙する必要がある場合、出力自体がO（n ^ 2）になる可能性があるためです。したがって、どのような作業アプローチでも、間隔を特定することさえできずに、何らかの方法で間隔を数える必要があります:-)。
O（N * LOG（N））は次のとおりです。
Ii=間隔i=（ai、bi）とします
L=区間のリストI
Lをaiで並べ替える
Lを半分にL1aとL2aに分割します。
L1aとL2aをbiで並べ替えて、L1bとL2bを取得します
マージソートL1bとL2bは、ネストの数を追跡します（たとえば、L1bのすべての間隔はL2bの間隔の前に開始するため、L1bのエンドポイントがl2bのエンドポイントよりも高いことがわかった場合、それらの間のすべてが内部にネストされていることがわかります-考えてみてください）。
これで、L2の間隔がL1の間隔内にネストされる頻度のカウントが更新されました。
L1とL2をマージした後、L1をL11aとl12aに分割し、L2をL21aとL21aに分割することにより、プロセス（再帰）を繰り返します。