难度: Hard
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：
输入：jobs = [3,2,3], k = 3 输出：3 解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：
输入：jobs = [1,2,4,7,8], k = 2 输出：11 解释：按下述方式分配工作： 1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11） 2 号工人：4、7（工作时间 = 4 + 7 = 11） 最大工作时间是 11 。
提示：
1 <= k <= jobs.length <= 121 <= jobs[i] <= 107运行时间: 36 ms
内存: 16.0 MB
class Solution:
def check(self, work_loads, jobs, i, limit):
if i >= len(jobs):
return True
cur_job = jobs[i]
for now_worker in range(len(work_loads)):
if work_loads[now_worker] + cur_job <= limit:
work_loads[now_worker] += cur_job
if self.check(work_loads, jobs, i + 1, limit):
return True
work_loads[now_worker] -= cur_job
# 如果加了cur job 就大于limit了的话，
# 或者如果我当前加入等于limit， 但后面不行的话，如果剩下的工作无法分配低于limit， 那再加一个肯定也不行。
if work_loads[now_worker] == 0 or work_loads[now_worker] + cur_job == limit:
break
return False
def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
if k >= len(jobs):
return max(jobs)
# 用递归的思路来看待问题， 怎么剪枝
# 先分配大的工作，然后分配小的工作
jobs.sort(reverse=True)
r = sum(jobs)
l = max(r // k, max(jobs))
while l < r:
mid = (l + r) // 2
work_load = [0 for _ in range(k)]
if self.check(work_load, jobs, 0, mid):
r = mid
else:
l = mid + 1
return l
该题解采用二分搜索与回溯的方法来解决问题。首先对工作时间数组进行排序，以便优先尝试分配耗时较长的工作，这有助于尽早达到最大工作时间的限制。在二分搜索的每一步，使用中值 'mid' 作为尝试的最大工作时间限制。在回溯部分，使用一个辅助函数 'check' 来递归尝试将每项工作分配给工人，直到所有工作都能在 'mid' 时间内被成功分配，或者无法分配为止。如果可以成功分配，则缩小搜索范围，否则增大 'mid'。通过这种方式逐步缩小可能的最大工作时间，直到找到最小可能值。
时间复杂度: O((log(sum(jobs) - max(jobs))) * k^n)
空间复杂度: O(n + k)
class Solution:
def check(self, work_loads, jobs, i, limit):
if i >= len(jobs):
return True
cur_job = jobs[i]
for now_worker in range(len(work_loads)):
if work_loads[now_worker] + cur_job <= limit:
work_loads[now_worker] += cur_job
if self.check(work_loads, jobs, i + 1, limit):
return True
work_loads[now_worker] -= cur_job
if work_loads[now_worker] == 0 or work_loads[now_worker] + cur_job == limit:
break
return False
def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
if k >= len(jobs):
return max(jobs)
jobs.sort(reverse=True)
r = sum(jobs)
l = max(r // k, max(jobs))
while l < r:
mid = (l + r) // 2
work_load = [0 for _ in range(k)]
if self.check(work_load, jobs, 0, mid):
r = mid
else:
l = mid + 1
return l
# Binary search to minimize the maximum work time
# Use recursion to distribute jobs and check if it fits within the limit
在这个问题中，下界`l`被设为`max(jobs)`，意味着无论工人数如何，单个工人至少需要能够完成最耗时的那项工作。这是因为每项工作必须完整地由一个工人来完成，无法分割。上界`r`被设为`sum(jobs)`，这代表了所有工作如果由一名工人完成所需要的总时间，是可能的最大工作时间。这个上界表示最坏情况，即所有工作由一个人完成的情况。这种设定帮助确保了二分搜索的范围覆盖所有可能的最优解。
在二分搜索中，将`r`设置为`mid`而不是`mid-1`是因为我们正在寻找最小可能的`mid`使得所有工作能够在此时间限制内完成。如果我们设置`r = mid - 1`，我们可能会错过这个最小的`mid`。通过设置`r = mid`，我们确保不会跳过这个界限，而是继续缩小搜索区间直到找到确切的最小界限。这种方法保证了`mid`始终是一个可能的解决方案，而不会因为过早缩小范围而错过正确答案。