algorithm - イベントスケジューリング 貪欲

Question

N 人の従業員が組織に存在する場合、N 範囲の日付オフセットが与えられます。1-4のようなもの
(つまり、従業員は 1 日目、2 日目、3 日目、4 日目に来ます)
2-6
8-9
..
1-14
各従業員がイベントに参加できるように、最小限の日数でイベントを開催する必要があります。これを行うアルゴリズム（おそらく貪欲）を提案してください。
PS: イベントは 1 日イベントです。

Answer 1

データが小さい場合は、総当たり攻撃を行うことができます。可能な 2 日間の組み合わせをすべて選択してください。組み合わせごとに試してみて、全員が両方に参加できるかどうかを確認してください。そうでない場合は、3 日間の可能な組み合わせをすべて選び、全員が 3 日間のうち 2 日間に参加できるかどうかを確認します。それは指数関数的ですが、あなたの目的にはそれほど悪くないかもしれません.

貪欲なアプローチは、毎日何人の人が働いているかを数え、人数が最も多い日を選ぶことです。繰り返しますが、まだ 2 つのイベントがスケジュールされていない人が毎日何人出勤しているかを数え、人数が最も多い日を選びます。もちろん、同じ日を 2 回選択しないでください。

Answer 2

これは、終了日でソートされたイベントに対する次の貪欲なアプローチによって実行できると思います

Maintain a num count for all intervals. (Initialize all to 0)
If num = 0 place the two events on the last two days of this interval. 
If num = 1 place one event on the last day of this interval
If num = 2 already two events have been covered for this interval.

間隔でイベントを配置すると、後続のイベントの数が増加する可能性があります。