事件调度贪婪
事件调度贪婪
提问于 2012-08-30 01:58:58
当组织中有N个员工时，我们会得到N个日期偏移量范围。就像这样
1-4 (即员工将在第一天、第二天、第三天和第四天来)
2-6
8-9
。。
1-14
我们必须在最少的天数内组织一个活动，这样每个员工至少可以参加活动，twice.Please建议算法(可能是贪婪的)来做到这一点。
PS:事件是一天的事件。
回答 2
Stack Overflow用户
发布于 2012-08-30 02:05:03
如果你的数据很小，你可以暴力破解它。选择所有可能的2天的组合。对于每种组合，尝试一下，看看是否每个人都能参加。如果没有，选择3天的所有可能的组合，看看是否每个人都能参加3天中的2天，以此类推。它是指数级的，但对你的目的来说可能不是那么糟糕。
贪婪的方法是计算每天有多少人在工作，并选择人数最多的一天。重复一遍，计算每天有多少人在工作，还没有安排两个活动，然后选择人数最多的一天。当然，不要把同一天选两次。
Stack Overflow用户
发布于 2012-11-28 02:20:37
我认为这可以通过以下贪婪的方法来完成，对事件按结束日期排序
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.在间隔中放置事件可导致后续事件的数目计数增加。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12183815
复制相关文章
相似问题
腾讯云开发者
