algorithm - いくつかの整数範囲を指定して、各範囲から少なくとも 1 つの整数を含む最小セットを見つける

Question

与えられた整数の範囲ごとに、セットに少なくとも1つの整数が含まれるように、最小数の整数のセットを見つけるにはどうすればよいですか。たとえば、これらの範囲が与えられた場合:

[0, 4], [1, 2], [5, 7], [6, 7], [6, 9], [8, 10]

次に、いくつかのソリューションセットは次のとおりです{ 1, 6, 8 }, { 2, 7, 9 }, { 1, 7, 8 } 。

Answer 1

予定表内で会議を描画するように、すべての範囲をend valueの順に描画するとします。

最初の数字が最初に終了するセグメントになるように、貪欲な方法で数字を視覚的に選択できます(この例では、それは になります2)。

次に、その番号を含むすべてのセグメントを消去し、最初からやり直します。

このアルゴリズムは解決策をもたらします{ 2, 7, 10 }

0  1  2  3  4  5  6  7  8  9 10
   ----
-------------
      ^        -------
      |           ----
                  ----------
                     ^  -------
                     |        ^
                              |

Answer 2

アルゴリズム: 開始点と終了点を並べ替えます。エンドポイントに到達するまでそれらを通過します。それを回答に追加し、開始点がすでに通過した (つまり、現在の終点を含む) すべての範囲を削除します。ポイントがなくなるまで繰り返します。

例：

[0, 4], [1, 2], [5, 7], [6, 7], [6, 9], [8, 10]

ソート後は

[0, [1, 2], 4], [5, [6, [6, 7], 7], [8, 9], 10], ans = []

最初のエンドポイントは です2]。それを追加して、ansその前に開いた範囲を削除します。つまり[0、 and [1:

[5, [6, [6, 7], 7], [8, 9], 10], ans = [2]

最初のエンドポイントは7]で、範囲を削除します[5, 7], [6, 7], [6, 9]:

[8, 9], ans = [2, 7]

最後に、最後の範囲を追加9して削除します。結果は になります[2, 7, 9]。

複雑：

並べ替えには O(nlogn) 時間がかかります。その後、各要素を 2 回渡します。1 回目は次の endpoing を探すとき、もう 1 回は現在開いている間隔をすべて削除するときO(nlogn)です。