活动安排贪婪

Question

当一个组织类似于
1-4（即员工将在第一天、第二天、第三天和第四天上班）
2-6
8-9
..
1-14
我们必须在最少的天数内组织一次活动，以便员工至少可以参加两次活动。请建议算法（可能是贪婪的）来做这件事
附言：活动是一天的活动。

Answer 1

如果你的数据很小，你可以强行使用。选择所有可能的2天组合。对于每种组合，尝试一下，看看是否每个人都能同时参加。如果没有，选择所有可能的3天组合，看看每个人是否都能参加3天中的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.

在一个间隔中放置事件会导致后续事件的计数增加。