用于检查超时的算法

Question

我有一组有限的任务需要由客户端完成。客户端在连接时被分配了一项任务，并在完成前一项任务后继续获得新任务。每个任务都需要由3个唯一的客户端完成。这样可以确保客户端不会对任务给出错误的结果。

然而，我不希望客户花费超过3000米的时间。由于某些任务相互依赖，这可能会阻碍进度。

问题是我在检查任务超时时遇到了问题——这应该在没有空闲任务的情况下进行。

此时，每个任务都有一个名为assignedClients的属性，如下所示：

assignedClients: [
{
client: Client,
start: Date,
completed: true
},
{
client: Client,
start: Date,
completed: true
},
{
client: Client,
start: Date,
completed: false
}
]

所有任务(大约1000个)都存储在一个数组中。基本上，当客户端需要一个新任务时，伪代码是这样的：

function onTaskRequest:
for (task in tasks):
if (assignedClients < 3)
assignClientToTask(task, client)
return
// so no available tasks
for (task in tasks):
for (client in assignedClients):
if (client.completed === false && Time.now() - client.start > 3000):
removeOldClientFromAssignedClients()
assignClientToTask(task, client)

但这似乎效率很低。有没有更有效的算法？

Answer 1

您想要做的是将任务存储在优先级队列(通常实现为堆)中，根据最旧的任务何时可用。当客户端需要新任务时，您只需查看队列的顶部即可。如果它可以被安排，那么它就可以被安排在该任务上。

当任务插入时，它现在被指定为其优先级。当你填写任务列表时，你会在最旧的客户端到期时将其放入

如果您使用的是堆，那么与当前的O(n)实现相比，所有操作都应该不比O(log(n))差。

您的数据结构看起来像JSON，在这种情况下https://github.com/adamhooper/js-priority-queue是我在谷歌搜索时发现的第一个优先级队列的JavaScript实现。在这种情况下，您的伪代码看起来像Pythonhttps://docs.python.org/3/library/heapq.html在标准库中。如果在您的语言中找不到实现，https://en.wikipedia.org/wiki/Heap_(data_structure)应该能够帮助您了解如何实现它