k-限定リソース用の欲張りアルゴリズム

Question

私は欲張りアルゴリズムを研究していますが、私は別のケースの解決策を考えています。

インターバルの選択問題では、相互に衝突しないアクティビティの最大数を選択したいので、最も早い終了時間でジョブを選択することができます。

もう1つの例。 n個の雇用を与えられており、できるだけ少ないリソースを購入したいと考えています。ここでは、すべてのジョブを左から右に並べ替えることができます。新しい開始点に出会うとカウンタを増やし、エンドポイントに出会うとカウンタを減分します。したがって、このカウンターから得られる最大の価値は、購入する必要があるリソースの数になります。

しかし、たとえばタスクがn個、リソースがk個の場合はどうなりますか？もっと多くのk資源を買う余裕がないのであればどうしますか？これを満たすためにできるだけ多くのタスクを削除するにはどうすればよいでしょうか？

また、私が書いた最後の問題の特定の名前がある場合は、それを聞いてうれしいです。

Answer 1

これは、リソースが1つしかないバージョンの一般的なケースのようです。

直感的には、ジョブを終了時刻で並べ替えて、順番に1つずつ取り出すのは理にかなっています。今、最後のジョブの終了時刻の代わりに、私たちのリソースに受け入れられた最後のk個のジョブの終了時刻を記録します。各ジョブについて、現在のジョブの開始時間が、リソースのいずれかの最後のジョブよりも大きいかどうかを確認します。そのようなリソースが見つからない場合は、そのジョブをスキップして先に進みます。 1つのリソースが見つかった場合、そのリソースにそのジョブを割り当てて終了時刻を更新します。そのジョブを実行できるリソースが複数ある場合は、最新の終了時刻を持つリソースに割り当てます。

私は本当にこの貪欲な戦略の証拠を持っていないので、間違っている可能性があります。しかし、私は、選択肢を変えることでより多くの仕事に合う可能性があるケースを考えることはできません。