異なるバージョンのインターバルスケジューリング

Question

n個のインターバルと数kが与えられた場合、それらのk個以上にポイントが含まれないようなインターバルの最大値サブセットを見つけるアルゴリズムを与えますか？ k = 1のとき、この問題は貪欲アルゴリズムで解決できることがわかります。私は上記の問題に対する貪欲なアルゴリズムを開発しようとしています。

Answer 1

私がこれにアプローチする方法は、最初にすべての間隔のすべての境界のセットを取得し、そのセットをソートすることです。これは多くてもn * 2点x_iの集合であってもよい。次に、集合S_i = [x_i、x_ {i + 1}]を考える。それぞれの開始間隔には、S_iが含まれているか、または分離しています。したがって、各S_iについて、集合を含むすべての区間のインデックスのリストT_iを構築することができる。したがって、間隔1,2,5はT_1 = {1,3,5}よりも集合S_1と交差する。

これで、集合T_iの集合が得られ、この問題は、T_i和集合Mが各T_iに対して最大でk個の要素を持つように、最小限の指標Mを見つけることに還元される。私たちは投げ捨てることによって問題を幾分単純化することができます.T_iはk個未満のアイテムから始まります。

再帰アルゴリズムはおかげでanswer.Thatのためにたくさんの素晴らしいアイデアです！しかし、最終的に、私はまだ、すべての可能なセットをチェックする必要が可能なセットM.