找出工人可以同时处理任务但必须等待开始的最短时间

Question

我遇到了类似leetcode 1732的问题，我可以找到解决方案。问题是这样的

您将获得一个整数数组

jobs

，其中

jobs[i]

是完成第

i

工作所需的时间。

您可以向

k

工人分配工作。每个工人可以同时处理 4 项任务。例如，当一个工人被分配任务

[1,2,3,4]

时，他们将需要 4 个单位的时间来完成。然而，每个工人必须等待几个单位的时间才能开始工作。假设

wait

是

k

数字的列表，每个数字都是等待时间。例如，如果

k[1] = 3

，工人 1 必须等待 3 个单位的时间才能开始。如果

k = 1

被分配为

[1,2,3,4]

，那么工人需要 4+3 = 7 才能完成。

求工人完成所有工作所需的最短工作时间。例如，假设

jobs = [3,3,4,2,9,8,5,6]

和

k = 2

，以及

wait = [9,11]

。我们可以将

[3,4,8,9]

分配给工人 1，将

[5,3,6,2]

分配给工人 2。那么完成所有工作所需的时间将为 18。

我对此完全一无所知，而且我不知道如何将其映射到 leetcode 1732（应该吗？）。我可以寻求帮助吗？

Answer 1

假设：

• 等待仅适用于每个工人一次，而不是每个工作一次
• 每当工人完成一项工作时，他们可以立即更换新的工作。
• 多名工人无法同时处理同一项工作，效果不佳。

将每个工作人员与 start_times 相关联，这是一个由四个整数组成的数组，全部初始化为该工作人员的等待时间。

按 min(start_times) 将所有工作人员放入最小堆中

反复：

• 弹出顶级工人
• min(start_times) 将重复 k 次，1 <= k <= 4.
• 获取 k 个最长的剩余作业，将 k 分钟开始时间（任意）增加这 k 个作业的长度，但将工作程序放回堆中。

执行上述操作时，请跟踪工作线程的 start_times 中出现的最大值。当我们完成后，这将是完成最后一项工作所需的时间。

运行时间：假设有n个工作和m个工人。每次我们弹出一个工人时，我们都会确定至少一项工作的完成时间。每次更新堆需要 log m 的努力，所以这是 O(n log m)