假设你需要为首席执行官安排会议。必须安排尽可能多的会议(计数,而不是会期)。
工作日有开始时间和结束时间。
有些时间没有时间(午餐等)
输入是一个时间列表。持续时间为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!)。
我希望有任何反馈和替代解决方案。谢谢!
发布于 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,这与等待排定的会议数无关。
https://stackoverflow.com/questions/28510436
复制相似问题