一次预约已满调度的算法

Question

我正在为一家管道公司构建一个日历调度应用程序。公司有一名或多名管道工，每个人都有一天不同时间的预约时间表。因此，乔什5月30日的日程安排可能包括上午10点30分钟的预约，下午1点45分钟的预约，下午3点的一小时预约，而玛丽亚那天的日程则完全不同。现在假设一个客户想在这家公司预约，而我的程序已经计算了这个新的约会所需的时间。我希望我的程序返回一个可能的预约时间列表，为任何水管工(S)。这类问题有标准的算法吗？

我更喜欢与语言无关的一般步骤，以便对任何可能处于类似情况的人提供更多帮助，尽管我使用的是PHP和PostgreSQL，如果有适合这种语言的特定语言特性的话。

到目前为止，我尝试过的是：

每个水管工在被要求的日期得到所有可用的班次

我已经了解到，这种方法的问题在于，它不知道如何处理比所要求的任命大得多的空白。如果你有一个从上午10点到下午6点的间隙，但你想要一个小时的预约，它只会建议上午10点到11点。这种方法也不允许日复一日的选择。在同样的情况下，如果客户想要一个早上的约会怎么办？那么它应该只建议10-11和11-12。或者，如果他们想要一个晚上的约会，应该只建议下午5-6点。这种方法也不考虑两个水管工一起工作。如果我们假设两名工人的工作时间是一半，那么也许算法应该在乔希和玛丽亚的时间表中寻找同样的30分钟，同时在两个水管工的时间表中找出60分钟的间隙。最后，该算法的效率很低。

顺便说一句，我在这里和互联网上看过其他几个关于如何解决类似情况的问题，但我发现大多数(如果不是全部)问题都涉及到优化日程安排。这对于这个程序的其他部分可能是有价值的，但是现在，让我们假设现有的任命是固定的和不可更改的。我们只是想把一个新的约会安排在现有的日程中。我知道这是可能的，因为像Calendly这样的应用程序具有类似的输入和输出。

简言之，是否有更好的方法来实现这些目标：

specified

• Suggest

• 建议，如果可能的话，在一个水管工的日程安排中，如果可能的话，只会在指定的时间(早上= 4-12，下午= 12-5，晚上= 5-10，夜晚= 10-4，或者任何一个)返回预约的可能性，如果不可能的话，继续使用该算法，就好像一天中没有一个时间是较小的间隙，其中n名水管工可能在1/n时间内完成这项工作(没有那么多水管工，因此没有必要对此设置一个限制)。这并不像其他标准那么重要，所以如果这是不可能的，或者会使算法变得更加复杂，那么就不用担心了。

• 将大的约会间隔分成更小的间隔，这样我们就可以在上午10点到下午2点之间建议4小时的间隔。显然，我们不能建议所有可能的长达一小时的间隙，因为它们将是无限的

。

提前谢谢你。

Answer 1

不需要任何复杂的算法。一天中只有一小部分可能的预约时间，比方说每隔30分钟左右。重复所有可能的时间: 06:00，06:30，07:00，. 20:00。每次检查是否符合要求时，该检查可以返回一个是/否结果，也可以返回一个数字，表示该时间匹配得有多好。最后，你会得到一份可能的预约时间列表，从中选出最好的一个或全部。