首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >预约调度算法

问预约调度算法
EN

Stack Overflow用户
提问于 2015-02-13 23:24:43
回答 1查看 2.5K关注 0票数 0

假设你需要为首席执行官安排会议。必须安排尽可能多的会议(计数,而不是会期)。

工作日有开始时间和结束时间。

有些时间没有时间(午餐等)

输入是一个时间列表。持续时间为30分钟、60分钟或90分钟。

My approach

将日表示为布尔数组。指数就是时间。每个数组索引代表30分钟。所以,天代表上午9点30分,day1代表上午9点30分day1 = true意味着9:30打开,如果为false则关闭。

有一个计数器变量来跟踪当前最早的空闲时间。每次迭代会议列表,查看当前的空闲时间+会议持续时间是否打开。运行时为O(N*N)。

缺陷

然而,我的方法并没有导致尽可能多的会议挤进一天。例如,我有120分钟的空闲区,以及可能的会议90、60和60分钟。我的算法首先迭代到90分钟的会议,并安排它,但有一个30分钟的免费块浪费。最好是把60分钟的会议都放进去。

另一个想法

获取所有潜在会议的组合,总持续时间不超过90分钟,并跟踪会议的最大数量。我相信这必须通过置换和O(N*N!)来完成。每个免费的街区。所以它的总运行时间是O(N *N* N!)。

我希望有任何反馈和替代解决方案。谢谢!

EN

回答 1

Stack Overflow用户

发布于 2015-02-14 01:38:33

我有一个新的算法给你们,这可能是相对简单的实现。第一,适合所有90分钟的会议,如果有些会议还剩下,他们将不适合。现在,通过60分钟的会议,并放置这些。如果你还有一些剩余时间,找一个30分钟窗口的90分钟会议(不可能有60分钟的窗口,或者会议会合适),然后用2次60分钟的会议来代替它。如果还有60分钟的会议,用3次60分钟的会议代替连续的2次90分钟的会议。如果还有60分钟的会议,用60分钟的会议代替任何90分钟的会议。然后去把30分钟的会议安排在空位上。如果还有剩余时间,用3x30分钟代替90分钟的会议。如果还有更多的剩余时间,就替换60分钟的会议。

据我从背包问题中知道的是,应该有一个多项式的解,这似乎适合,所以如果这是可行的,.另外,如果n是计划中的空闲时隙数,则上限为6*n^2,这与等待排定的会议数无关。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/28510436

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档