私はこの質問を解決しようとしていますが、これを機能させる方法に行き詰まっています。質問を投稿してから、私がどこにいるのかを説明します。
合計サイズ n の一連の水平線分と垂直線が与えられた場合、各垂直線が交差する水平線分の数を計算します。アルゴリズムは複雑さ O(n*logn) である必要があり、並べ替えとそれに続く線形スキャンによって実現する必要があります。水平線分は 2 つの x 座標と y 座標で指定され、垂直線は 1 つの x 座標で指定されます。出力は、数値 count[l] の配列で、垂直線 l ごとに 1 つです。
並べ替えについては、線が最も早く終了するセット全体を並べ替えると思います (つまり、最小の 2 番目の x 座標、または垂直線の場合は 1 つの x 座標のみ)。すべての行。並べ替えに続く線形スキャンをどのように実行するかについて、私は混乱しています。誰かがヒント、ヒント、またはガイドラインを持っていれば、私はそれを感謝します!
PS: これは中間テストの練習なので、必ずしも宿題ではありませんが、宿題としてマークします。
質問は別の方法で書くことができます：
水平セグメント（x1、x2）ごとに、それと交差するすべての垂直線を見つけます。これを行うには、位置xのセットを取得する垂直線を並べ替えます。
ここで、二分探索を実行し、xのセットでx1を配置し、その位置をp1と呼びましょう。x2、p2についても同じようにします。指定されたセグメントの交差の数はp2-p1に等しくなります。
すべての水平セグメントに対してそれを行います。
垂直セグメントの並べ替えにはO（klog（k））が必要です。すべての検索はO（log（k））で実行され、セグメントごとに2回実行されます：O（mlog（k））。ここで、kは垂直線の数、mは水平セグメントの数です。n = m + k> m、kであるため、全体的な複雑さはO（nlogn）です。
最初に、水平セグメントのすべての始点/終点を配置します。および垂直線の x 座標を一緒に。
次に、並べ替えます。sorted list と呼びましょうL。
L3番目に、ポイントリストの左端から始まり、右に移動する垂直走査線があることをイメージングします。
走査線が点に当たると、それは水平セグメントの始点、水平セグメントの終点、または垂直線のいずれかになります。
また、走査線を移動すると、次の 2 つのことができます。
1) 走査線が現在交差している水平セグメントのセットを保持します (それが水平セグメントの始点/終点であるときはいつでも、セットに追加/セットから削除します)
2) 垂直線の場合は常に、1) で維持しているセット内のすべての水平セグメントと垂直線が交差していることがわかります。
したがって、並べ替えは O(nlogn); です。並べ替えられたリストを介して走査線を移動することLは O(n) です
全体として、それは O(nlogn) です