在 Python 中找出完成所有给定约束条件的工作的最短时间

pythonserver side programmingprogramming更新于 2025/10/10 19:56:17

假设我们有一组具有不同时间要求的工作，有 k 个不同的人来分配工作，并且我们还有受让人完成一个工作单元需要多少时间。我们必须找到在以下约束条件下完成所有工作所需的最短时间。

只能为受让人分配连续的工作。
两个受让人不能共享或执行单个工作。

因此，如果输入为 k = 4、t = 5、job = {12, 6, 9, 15, 5, 9}，则输出将为 75，因为我们通过分配 [12]、[6, 9]、[15] 和 [5, 9] 获得此时间。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 is_valid() 。这将花费时间，K，作业
n := 作业大小
count := 1, curr_time := 0, i := 0
while i < n, do
- if curr_time + job[i] >时间，然后
  - curr_time := 0
  - count := count + 1
- 否则，
  - curr_time := curr_time + job[i]
  - i := i + 1
当 count <= K 时返回 true
从 main 方法，执行以下操作 <
n := size of job
end := 0, begin := 0
对于范围从 0 到 n 的 i，执行
- end := end + job[i]
res := end
job_max := job 的最大值
当 begin <= end 时，执行
- mid := ((begin + end) / 2) 取整数部分
- 如果 mid >= job_max 且 is_valid(mid, K, job) 为真，则
  - res := res、mid 的最小值
  - end := mid - 1
- 否则，
  - 开始:= mid + 1
返回 res * T

示例

让我们看看下面的实现以便更好地理解 −

def is_valid(time, K, job):
   n = len(job)
   count = 1
   curr_time = 0
   i = 0
   while i < n:
      if curr_time + job[i] > time:
         curr_time = 0
         count += 1
      else:
         curr_time += job[i]
         i += 1
   return count <= K
def get_minimum_time(K, T, job):
   n = len(job)
   end = 0
   begin = 0
   for i in range(n):
      end += job[i]
   res = end
   job_max = max(job)
   while begin <= end:
      mid = int((begin + end) / 2)
      if mid >= job_max and is_valid(mid, K, job):
         res = min(res, mid)
         end = mid - 1
      else:
         begin = mid + 1
   return res * T
job = [12, 6, 9, 15, 5, 9]
k = 4
T = 5
print(get_minimum_time(k, T, job))