在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