各区間が [l,r] の形式である閉区間のセットが与えられたとします。このセットから 2 つの間隔を選択する場合、それらの交差のサイズに和集合のサイズを掛けた値が最大になります。この問題を解決するための重要なアルゴリズムを提供できますか?
たとえば、[1,6]、[4,8]、[2,7]、[3,5] の 4 つの区間があるとします。最適な解決策は、[1,6] と [2,7] を選択することです。答えは (7-1) * (6-2) = 24 です。
実際には、元の問題では (N>=2) 個の間隔を選択する必要がありますが、最適解は 2 つの間隔のみで構成されることを証明できると思います。
最適解に区間が 3 つ以上ある場合:
[ ]
[ ]
[ ]
中間区間を削除しても重みが減らないことがわかります。
結合時間の交差を最大化すると思われる N > 2 のオーバーラップする間隔のセットが与えられた場合、結合の左端の点を含む間隔と結合の右端の点を含む間隔を確保します。N > 2 であるため、少なくとも 1 つの間隔が残っています。セットからこの間隔を削除しても、間隔の和集合のサイズは小さくなりません。これは、間隔を確保して左端と右端の点をカバーするためです。間隔を削除することによってのみ、交差のサイズを大きくすることができます。したがって、この間隔を削除すると、最大化しようとしている積を増やすことしかできないため、実際に最適な解は N = 2 で見つけることができます。
区間のエンドポイントのセットを並べ替え、昇順で調べます。同点の場合は、右端のポイントの前に左端のポイントを考慮します。間隔のセットを追跡し、左端のポイントが表示されたときにセットに間隔を追加し、右端のポイントが表示されたときにセットから間隔を削除します。
任意の 2 つのオーバーラップする間隔については、そのうちの 1 つが既に存在し、もう 1 つを追加しようとしている時点があります。したがって、間隔をセットに追加する直前に、それをセット内の他のすべての間隔と比較すると、重複する間隔のすべてのペアを比較できます。したがって、追加しようとしている間隔とセット内の他のすべての間隔との和と交差の積を計算し、見られる最大のものを追跡できます。
2 つの区間で十分であることの証明:別の区間に適切に含まれる区間を選択しても意味がありません。一般性を失うことなく、区間を [a1, b1], ..., [an, bn] とし、a1 < ... < an とします。別の間隔を適切に含む間隔がない場合、b1 < ... < bn. i < j < k の場合、([ai, bi] 交差 [aj, bj] 交差 [ak, bk]) = ([ai, bi] 交差 [ak, bk]) が成立し、結合についても同じであるため、 3 つ以上の間隔を選択する理由はありません。
O(n log n)-time アルゴリズム:再定式化された問題は、(d - a) * (b - c) を最大化する間隔 [a, b] および [c, d] を見つけることです。交差しないでください。私たちのアルゴリズムは O(n log n) の前処理を行うことで、O(log n) 時間で各間隔の最良の仲間を見つけることができます。
[a, b] のベストメイトを探してみましょう。いくつかの代数を実行します: (d - a) * (b - c) = d*b - d*c - a*b + a*c. a、b は固定されているため、-a*b 項を削除して、すべての区間 [c, d] で内積 <(a, b, 1), (d, c, -d*c)> を最大化できます。ベクトルのセット (d, c, -d*c) は固定されているため、これは基本的に、静止多面体と (a, b, 1) に垂直な移動平面の衝突をシミュレートしています。Edelsbrunner と Maurer ( 3 次元で極値を見つけ、平面で郵便局の問題を解決する、1984 年) のおかげで、時間 O(n log n) で前処理し、このタイプのクエリを異なる a と b について解決するアルゴリズムがあります。 O(log n) 時間で。
残念なことに、少なくとも 2 つの間隔を選択する必要がありますが、最良の "解決策" は、それ自体で最も長い間隔である可能性があります。面倒ですが、Edelsbrunner (マウラー) を拡張して、同じ実行時間で 2 番目に極端な点を見つけることは可能であると確信しています。