事件调度

Question

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

Answer 1

我认为这可以通过以下贪婪的方法来完成

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 count增加。

Answer 2

如果你的数据很小，你可以强行使用它。选择所有可能的2天组合。对于每种组合，尝试一下，看看是否每个人都可以同时参加。如果没有，选择所有可能的3天组合，看看是否每个人都可以参加3天中的2天，依此类推。这是指数级的，但对你来说可能没那么糟糕。

贪婪的方法是计算每天有多少人在工作，然后选择人数最多的一天。重复一遍，数一数每天有多少人没有安排两个活动，然后选择人数最多的一天。当然，不要选择同一天两次。