在已经排满的日程表中安排一次预约的算法

Question

我正在为一家管道公司建立一个日历调度应用程序。该公司有一个或多个水管工，他们每个人都有一个全天不同时间的预约时间表。所以Josh在5月30日的日程安排可能包括上午10点30分钟的预约，下午1点45分钟的预约，以及下午3点一个小时的预约，而Maria当天的日程安排则完全不同。现在假设一个客户想向这家公司预约，而我的程序已经计算出了这个新的预约所需的时间。我希望我的程序能够返回一个列表，列出任何水管工可能的预约时间。这种类型的问题有标准算法吗？

我更喜欢语言无关的、通用的步骤，只是为了对使用不同语言可能遇到类似情况的人更有帮助，尽管我使用的是PHP和PostgreSQL，如果有适合这个问题的特定语言特性的话。

以下是我目前尝试过的方法。

1. 获取每个水管工在要求的那一天的所有可用班次
2. 获取当日已完成的所有预约
3. 做一种布尔减法，把预约的班次剪掉，在每个水电工的日程表上留下空隙
4. 摆脱所有小于所要求的预约长度的时间表差距（我还在这里计算开车时间，这样我就知道预约之间需要多远了
5. 将这些空白返还给客户，修剪成预约长度，作为预约的可能性。

我了解到，这种方法的问题在于，它不明白如何处理比要求的预约时间大得多的空隙。如果你有一个从上午10点到下午6点的空档，但你想要一个小时的预约，它只会建议上午10点到11点。这种方法也不允许选择时间日期。在同样的场景下，如果客户想预约上午的时间呢？那么它应该只建议10-11和11-12。或者如果他们想预约晚上的时间，那么应该只建议下午5-6点。这种方法也没有考虑两个水电工一起工作的情况。如果我们假设两个工人=一半的时间，那么也许算法应该在Josh和Maria的日程表中寻找同样的30分钟可用时间，同时在任一水管工的日程表中寻找60分钟的空隙。最后，这个算法感觉效率很低。

顺便说一下，我在这里和互联网上看了其他几个关于如何解决类似情况的问题，但我发现这些问题中的大多数（如果不是全部）都涉及到优化时间表。这对这个程序的其他部分可能是有价值的，但现在，让我们假设现有的约会是固定的和不可改变的。我们只是想把一个新的约会适合于现有的时间表。我知道这是可能的，因为像Calendly这样的应用程序有类似的输入和输出。

简而言之，有没有更好的方法来实现这些目标。

• 建议在一个水管工的日程表上 给出一个时间间隔的空档期。
• 如果可能的话，只返回一天中给定时间内的预约可能性（上午=4-12，下午=12-5，晚上=5-10，晚上=10-4，或任何时间），如果不可能，则继续算法，就像没有指定一天中的时间一样。
• 提出较小的差距，n个水管工可能会在1n个时间内完成工作（没有那么多水管工，所以设置一个限制没有必要）。这并不像其他标准那么重要，所以如果这不可能或者会让算法复杂得多，那就不用担心。
• 将大的预约间隙分割成更小的间隙，这样我们就可以在上午10点到下午2点之间建议4个小时长的间隙。显然，我们不能建议该间隙的所有可能的一小时段，因为它们会是无限的

先谢谢你。

Answer 1

没有必要使用任何复杂的算法。一天中只有少量可能的预约时间，比方说每30分钟左右一次。迭代所有可能的时间。06:00, 06:30, 07:00, ... 20:00. 检查每一次是否符合要求，检查的结果可以是yesno，也可以是一个数字，表示该时间的匹配度。你最终会得到一个可能的预约时间列表，选择一个最好的或者全部的时间。