在Python中找到在给定约束下完成所有作业的最短时间

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

• 只能为受让人分配连续的工作。

• 两个受让人无法共享或执行一项工作。

因此，如果输入像k = 4，t = 5，作业= {12，6，9，9，15，5，9}，那么这次我们通过分配[12]，[6 ，9]，[15]和[5，9]

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

• 定义一个函数is_valid()。这需要时间，K，工作

• n：=工作规模

• 计数：= 1，curr_time：= 0，i：= 0

• 当我<n时

• curr_time：= curr_time +工作[i]

• 我：=我+ 1

• curr_time：= 0

• 数：=数+ 1

• 如果curr_time + job [i]>时间，则

• 除此以外，

• 当count <= K时返回true

• 在主要方法中，执行以下<

• n：=工作规模

• 结束：= 0，开始：= 0

• 对于0到n范围内的i，执行

• 结束：=结束+工作[i]

• res：=结束

• job_max：=最大工作

• 在开始<=结束时，执行

• 开始：=中+ 1

• res：=最小res，中

• 结束：=中-1

• 中：=（（begin + end）/ 2）取整数部分

• 如果mid> = job_max并且is_valid(mid,K,job)为true，则

• 除此以外，

• 返回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))

输入值

4, 5, [12, 6, 9, 15, 5, 9]

输出结果

75