想定される面接の質問 重なり合う区間をすべて求める方法

質問内容

面接の質問ではない それ自体

これはインタビューの質問ではありませんが、私のプロジェクトで出会ったものです。

あなたはN組の区間（例えば整数）を持っています。 あなたは、O(N)時間で互いに重複するすべての間隔を特定することを要求されています。例えば、あなたが

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

の場合、答えは {1, 3}, {12, 14}, {2, 4}, {13, 15} となります。なお、グループ化する必要はないので、結果は例のようにどのような順序でも構いません。

KMPアルゴリズムが文字列検索にO(N)の時間を要するので、O(N)の時間を投入しただけです。 :D

私が考え出した最高のもので、今プロジェクトで使っているものは O(N^2) です。ええ、ブルートフォースはかなり悲しいですが、誰も文句を言わないので、私はそれをリファクタリングしません。 :P それでも、私は、より大きな頭がより優雅な解決策を持っているかどうか知りたいと思いました。

どのように解決するのですか?

区間の終点を配列に放り込み、始点か終点のどちらかに印をつけます。区間が閉じている場合は始点より終点を、半開きの場合はその逆にして、同点を解消することでソートします。

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

次に、リストを通して反復し、いくつのインターバルにいるかを追跡します（これは処理された開始点の数から終了点の数を引いたものに等しい）。すでにインターバルに入っているときに始点にぶつかると、これはインターバルが重なっていることを意味します。

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

端点にデータを並べて保存し、どの区間にいるのかを記録しておくことで、どの区間がどの区間に重なっているのかがわかります。

これはO(N logN)の解であり、ソートが主な要因である。