LeetCode 1723: 完成所有工作的最短时间

给你一个整数数组 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 。

一看是一个hard题目，心已经凉了半截，先试试朴素的方法求解。

感性地理解，如果要求将大任务和小任务都分配到人上，优先放入大任务更容易使得工作变得简单。
在任务分配过程中，优先分配工作量小的工作会使得工作量大的工作更有可能最后无法被分配。

给每个人建立一个已分配任务的耗时统计数组time，index为人的编号，value已分配任务的总时长
将工作按时间从大到小排序
每次把当前最大的工作分配给当前总工作时间最少的工人

这种方法简单但不一定能得到最优解，但是对于某些case应该是能通过的。问了一下GPT，原来这个是贪心算法。

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法的特征：

局部最优选择: 每一步都做出当前看起来最好的选择

不可取消: 一旦做出选择就不能反悔

不回溯: 不会根据后续结果调整之前的选择。

再分配任务的过程中

贪心选择: 每次都将当前工作分配给目前工作时间最少的工人

局部最优: 这种分配方式在当前时刻是最优的（让负载最轻的工人承担新工作）

不可回溯: 一旦工作被分配就不会重新调整

/// 解法：使用贪心算法求解（可能不是最优解）
class Solution {/// 计算完成所有工作的最短时间（贪心方法）/// - Parameters:///   - jobs: 工作数组，每个元素表示一个工作的耗时///   - k: 工人数量/// - Returns: 分配方案下的最大工作时间func minimumTimeRequired(_ jobs: [Int], _ k: Int) -> Int {// 记录每个工人的工作时间var time: [Int] = []// 初始化k个工人的工作时间为0for _ in 0..<k {time.append(0)}// 将工作按照耗时从大到小排序let sortJobs = jobs.sorted().reversed()// 贪心策略：每次将当前工作分配给工作时间最少的工人for job in sortJobs {let (index, _) = self.findMinValueAndIndex(time)time[index] += job}// 返回所有工人中的最大工作时间return time.max()!}/// 查找数组中的最小值及其索引/// - Parameter array: 输入数组/// - Returns: 包含最小值索引和值的元组private func findMinValueAndIndex(_ array: [Int]) -> (index: Int, value: Int) {guard var minValue = array.first else { return (0, 0) }var minIndex = 0// 遍历数组找出最小值和对应索引for (index, value) in array.enumerated() {if value < minValue {minValue = valueminIndex = index}}return (minIndex, minValue)}
}

跑了一下，一个62个用例，通过了52个测试用例，占比80%，确实不是最优解，但是也是一个比较好的思路。

思路2

答案一定在特定区间内

下界：单个工作的最大耗时
上界：所有工作的总耗时

在这个范围内寻找，一定能找到最终解。在范围内寻找，可以使用二分法不断缩小边界。

需要解决的核心问题是：在给定时间限制下，能否将所有工作分配给 k 个工人？

先假定给到第i个工人，然后看是否能满足条件，需要不断的递归调用，直到所有任务都分配完成。

/// 函数：判断在给定时间限制下是否能分配所有工作
/// - Parameters:
///   - jobs: 排序后的工作数组
///   - index: 当前处理的工作索引
///   - limit: 时间限制
///   - workload: 每个工人当前的工作量
/// - Returns: 是否能够成功分配所有工作
private func canDistribute(_ jobs: [Int], _ index: Int, _ limit: Int, _ workload: inout [Int]) -> Bool {// 第i项工作已经分配完成 -> 所有工作都已分配, if index >= jobs.count {return true}let currentJob = jobs[index]// 尝试将当前工作分配给每个工人，for i in 0..<workload.count {if workload[i] + currentJob <= limit {  // 当前工人可以接受这份工作workload[i] += currentJob           // 分配工作// 递归调用自己，继续分配下一份工作if canDistribute(jobs, index + 1, limit, &workload) {  return true}workload[i] -= currentJob           // 回溯：撤销分配}// 优化：如果当前工人未被分配工作，后续工人也不需要尝试if workload[i] == 0 {break}}return false
}

注意是尝试将当前工作分配给每个工人，并且分配不成功时会撤销分配，通过这种方式，会尝试把尝试把工作i给到每个工人身上，最大循环次数是 jobs.count * k 次，相当于穷举了。

虽然最大循环次数是jobs.count * k ，但是有一些优化策略可以帮助我们减少一些不必要的循环

工作排序

将工作按照耗时从大到小排序
大工作先分配可以提早触发限制条件

剪枝优化

每个工人都是等价的，如果某个工人未被分配工作，后续工人也无需尝试

状态记录

使用 `workload` 数组记录每个工人的当前工作量
通过回溯维护状态的正确性，避免重复计算

有了核心判断方法，在加上二分查找，不断缩小边界，最终实现如下：

/// 解法：使用二分查找 + 回溯的方法求解
class Solution {/// 计算完成所有工作的最短时间/// - Parameters:///   - jobs: 工作数组，每个元素表示一个工作的耗时///   - k: 工人数量/// - Returns: 最优分配方案下的最大工作时间func minimumTimeRequired(_ jobs: [Int], _ k: Int) -> Int {// 对工作按耗时从大到小排序，有助于提早触发限制条件let sortedJobs = jobs.sorted(by: >)// 二分查找的下界：单个工作的最大耗时var left = sortedJobs[0]// 二分查找的上界：所有工作的总耗时var right = jobs.reduce(0, +)// 二分查找过程while left < right {let mid = left + (right - left) / 2// 记录每个工人的工作量var workload = Array(repeating: 0, count: k)// 判断是否能在mid时间限制内分配所有工作if canDistribute(sortedJobs, 0, mid, &workload) {right = mid    // 可以完成，尝试减小限制} else {left = mid + 1 // 不能完成，增加限制}}return left}/// 回溯函数：判断在给定时间限制下是否能分配所有工作/// - Parameters:///   - jobs: 排序后的工作数组///   - index: 当前处理的工作索引///   - limit: 时间限制///   - workload: 每个工人当前的工作量/// - Returns: 是否能够成功分配所有工作private func canDistribute(_ jobs: [Int], _ index: Int, _ limit: Int, _ workload: inout [Int]) -> Bool {// 基准情况：所有工作都已分配完成if index >= jobs.count {return true}let cur = jobs[index]// 尝试将当前工作分配给每个工人for i in 0..<workload.count {// 如果当前工人添加这份工作后未超过限制if workload[i] + cur <= limit {workload[i] += cur  // 分配工作// 递归分配下一份工作if canDistribute(jobs, index + 1, limit, &workload) {return true}workload[i] -= cur  // 回溯：撤销分配}// 优化：如果当前工人未被分配工作，后续工人也不需要尝试if workload[i] == 0 {break}}return false}
}