用Ruby/Rails进行约会安排

Question

我正在使用Rails开发一个呼叫中心软件，需要为能够为客户处理电话的代理安排预约。在考虑到呼叫中心软件的情况下，需要确保尽可能利用整个代理的日程安排，留出最少量的空隙（即代理没有预约的时间段）。

给定代理的日程安排，例如一天的上午9:00到下午5:30，其中午休息30分钟，从下午1:00到1:30，我需要安排不同时长的预约，有些是60分钟，有些是90分钟。

如果由于某种原因，午餐时间在日程安排中留下了一些空隙，我应该能够将午餐时间向前或向后移动30分钟，因此它可以在下午1:30到2:00或中午12:30到1:00之间移动。

我开始创建午餐休息作为一种约会，这将提供移动starts_at和finishes_at属性的灵活性。约会要么是60分钟，要么是90分钟，这是30分钟的倍数，午餐也是30分钟，我开始将代理日程拆分为每个30分钟的时间段。

因此，对于给定代理在给定日期，查看他的日程安排，我实例化了一个时间段数组，每个时间段持续30分钟，starts_at和finishes_at属性类似于9:00AM - 9:30AM，9:30AM - 10:00AM等。

我需要帮助循环遍历此约会时间段数组，并拉取2个连续的时间段或3个连续的时间段，具体取决于60或90分钟的预约时长，同时需要考虑能够将午餐时间向前或向后移动30分钟。

非常感谢您的任何帮助。

- Dharam Gollapudi

Answer 1

看一下您的问题：

1. 预约时间为60或90分钟。
2. 午餐时间在12:30-2:00之间，时长可变。

我们希望尽量减少没有预约的时间。

现在，您有一个需要填充的时间段，从早上9点到下午5点半。假设预约时间在9:00-5:30之间，我们可以使用基于最早完成时间的贪心算法进行区间调度（参考来源），并考虑您的额外约束。

基本上，该算法如下（伪代码）：

Let R be the set of all appointments
Let R11 be the set of appointments from R before 12:30 that are compatible with 12:30-1:00 and R12 be the set of appointments from R after 1:00 that are compatible with 12:30-1:00
Let R21 be the set of appointments from R before 1:00 that are compatible with 1:00-1:30 and R22 be the set of appointments from R after 1:30 that are compatible with 1:00-1:30
Let R31 be the set of appointments from R before 1:30 that are compatible with 1:30-2:00 and R32 be the set of appointments from R after 2:00 that are compatible with 1:30-2:00

Let R1Comb = findSet(R11) + 12:30-1:00 + findSet(R12)
Let R2Comb = findSet(R21) + 1:00-1:30 + findSet(R22)
Let R3Comb = findSet(R31) + 1:30-2:00 + findSet(R32)

Function findSet(R) 
    Let A be the time interval to fill    
    While R is not empty
        Choose a request r in R that has the smallest finishes_at
        Add r to A
        Remove all appointments in R that are not compatible with r
    EndWhile
    Return A
EndFunction

Return the R that has the smallest amount of holes in R1Comb, R2Comb, R3Comb

这个算法利用了几个概念：

1. 如果约会r1与r2重叠，则它们不兼容。
2. 由于#1，我们知道i=1,2,3的Ri1/Ri2将不会相互冲突。因为如果Ri2中的一个约会与Ri1不兼容，则它也与午餐时间不兼容，这是一个矛盾，因为我们去掉了所有不兼容的约会。
3. 一旦我们拆分了约会集合，那么就是解决两个调度问题的问题，可以贪心地解决。

这个算法仍然是O(n log n)，因为你进行了6次贪心算法（一个常数），每次贪心迭代都是O(n log n)，而第一行和最后一行都是O(n)。

人们写论文来讨论调度问题，并不是一个简单的问题。我建议您查看http://www.asap.cs.nott.ac.uk/watt/resources/university.html以获得更好的理解。

祝你好运 :)

- vinceh

---

@vinceh- 感谢您详细的解释和提供相关部分的链接。在查看您提供的贪心算法链接之前，我没有意识到这个问题的复杂性。此外，我以最简单的方式呈现了问题，删除了其他要求，包括某些类型的约会安排（有点像午餐休息，但不是午餐休息，被视为低优先级），持续时间为30分钟，应该在整天内移动以适应其他高优先级约会。如果考虑所有要求的话，我无法想象它的复杂性。 - Dharam Gollapudi