algorithm - 事件调度贪心

Question

当组织中有 N 个员工时，我们会得到 N 个日期偏移范围。像
1-4 （即员工将在第 1、2、3 和 4 天来）
2-6
8-9
..
1-14
我们必须在最少天数内组织一次活动，以便每个员工都可以参加活动至少两次。请建议算法（可能是贪婪的）来做到这一点。
PS：活动为一日活动。

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.

以间隔放置事件可能会导致后续事件的 num 计数增加。