すべての重複する間隔を見つける

1. 概要

このチュートリアルでは、重複する間隔とそれらを検出する方法について説明します。

最初に、重複する範囲を見つける問題を紹介します。その後、問題を解決するための2つのアプローチを紹介します。

2. 定義

まず、範囲の重複の概念を紹介しましょう。次に、この記事で説明する問題を提示できます。

2.1. 重複する間隔

1から。までの番号が付けられた固定点を持つ線があるとします。この線に沿って、この線の一部をカバーする複数の範囲があります。重複する間隔と重複しない間隔を定義する必要があります。

アイデアを説明するために、次の重複する間隔の例を見てみましょう。

両方の範囲に少なくとも1つの共通点がある場合、それらは重複していると言います。 つまり、次の場合、2つの範囲が重複していると言います。

一方、重複しない範囲には共通点がありません。重複しない範囲の例を見てください。

次の場合、2つの範囲が重複しないと言います。

重複する範囲の意味が理解できたので、次に問題を説明します。

2.2. 問題の定義

この問題では、範囲が与えられます。少なくとももう1つと重複している範囲の数を数える必要があります。さらに、これらの重複する範囲をすべて返すように求められます。

次の例を見てみましょう。

この例の答えは間隔{}です。その理由は、これらの各間隔が少なくとも1つの他の間隔と重複しているためです。

たとえば、範囲3は1および2とオーバーラップします。同様に、範囲5は6とオーバーラップします。

ただし、範囲4は他の範囲と重複しません。したがって、それは答えに提示されていません。

3. 素朴なアプローチ

このアプローチでは、他のすべての間隔で各間隔をチェックします。重複が見つかったら、この間隔が他の間隔と重複しているため、回答に追加する必要があることを示します。

実装を見てください：

まず、可能なすべての範囲で反復します。範囲ごとに、他のすべての範囲を繰り返し処理して、両方が重複しているかどうかを確認します。重複を見つけることができた場合は、現在のものを回答に追加します。

それ以外の場合、現在の間隔が他の間隔と重ならない場合は、単に次の間隔に進みます。

素朴なアプローチの複雑さはです。ここで、は間隔の数です。

4. スイープラインアプローチ

スイープラインアプローチの理論的考え方を説明してから、アルゴリズムの実装にジャンプします。

4.1. 理論的アイデア

-軸座標に指定されたすべての間隔を表示したとします。さて、始めて前進します。途中で見つけようとしているイベントを調べてみましょう。

遭遇する可能性のあるイベントには2つのタイプがあります。最初のイベントは、特定の間隔の始まりです。同様に、他のイベントは間隔の終わりです。ただし、-軸に沿って移動している間、現在の状態を保存する必要があります。

そのために、現在開いている範囲を維持します。オープンレンジとは、最初は見つけたものの、まだ終わりに達していないものを意味します。

-軸に沿って移動している間、2つのケースがあります。

最初のケースは、新しい間隔の開始に遭遇した場合です。まだオープンレンジがない場合は、見つかったレンジを現在オープンレンジとして保存するだけです。それ以外の場合、オープンレンジがある場合は、オーバーラップが検出されたことを意味します。したがって、オープンレンジと新しく見つかったレンジの両方を回答に追加します。また、保持しているオープンレンジを更新する必要があります。

エンディングができるだけ右にあるものを維持することが常に最適です。その理由は、私たちが立っている場所から開始して、より長い距離をカバーするためです。したがって、現在開いている間隔として、終了が大きいものを保持します。

一方、範囲の終わりに遭遇した場合は、これがである範囲を確認する必要があります。現在開いている範囲とは異なる範囲の場合は、無視します。それ以外の場合、現在のオープンレンジが終了している場合は、現在オープンレンジをクリアして、これ以上オープンレンジがないことを示します。

4.2. 実装

スイープラインアプローチの実装を見てみましょう。

まず、各区間のすべての開始点と終了点をリストに追加します。間隔ごとに、ポイント、ポイントのタイプ、およびそのインデックスを追加します。

次に、リストを並べ替えます。注意してくださいリストの並べ替えは、ポイントに基づいて行う必要があります。 2つの要素が同じポイントを持っている場合、タイプに基づいてそれらをソートする必要があります。そのように、タイプが始点であるものが最初に来る。その理由は、要素をウォークスルーするため、現在開いている間隔を閉じる可能性のある終了を検出する前に、開始を検出する必要があるためです。

ポイントとタイプの両方が等しい場合、要素を任意の順序で並べ替えることができます。

その後、繰り返します。現在の要素が間隔の始まりであり、現在開いている範囲がない場合、これを現在開いている範囲として保存します。それ以外の場合は、見つかった範囲を回答に追加します。

また、現在開いているものを回答に追加する場合もあります。現在のオープン間隔がすでに回答に追加されているかどうかを判断するために使用することに注意してください。

また、両方の間隔を比較して、末尾が大きい方を保存します。

ただし、インターバルの終わりに到達し、それが現在開いているものと同じである場合、現在開いているものをクリアします。

最後に、答えを返します。

スイープラインアプローチの複雑さはです。ここで、は範囲の数です。複雑さは、並べ替え操作によるものです。

4.3. 例

セクション2.2と同じ例を見てみましょう。

アルゴリズムのステップの順序をリストしてみましょう。

間隔1の開始：開いている範囲がないため、現在開いている範囲として1を格納します。
間隔3の始まり：現在開いている範囲があることに気づきました。したがって、両方を回答に追加します。また、区間3は、末尾が大きいため、現在開いている区間として保存します。
インターバル1の終わり：現在開いているものではありません。したがって、それを無視します。
インターバル2の始まり：現在オープンレンジがあります。したがって、重複を検出し、範囲2を回答に追加します。インデックス3はすでに追加されているため、追加しません。また、現在開いている範囲2を維持します。
間隔3の終了：現在開いている範囲ではないため、無視します。
インターバル2の終了：現在開いている範囲なので、クリアします。
間隔4の開始：現在開いている範囲がないため、範囲4を開いている範囲として格納します。
インターバル4の終わり：現在開いている範囲です。だから、私たちはそれをクリアします。
インターバル5の始まり：現在開いている範囲はありません。したがって、現在開いている範囲として範囲5を格納します。
間隔6の開始：オーバーラップを検出します。したがって、範囲5と6の両方を回答に追加し、現在開いている間隔を間隔6に更新します。
インターバル5の終了：現在開いているものではないため、無視します。
インターバル6の終了：終了に達したため、現在開いている範囲をクリアします。