給你一個整數數組 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}
}

通過這種方式確實找到了最優解。

時間復雜度分析

• 二分查找：O(log(sum))，其中 sum 是工作總時間?
• 回溯過程：O(k^n)，其中 n 是工作數量，k 是工人數量
• 總體復雜度：O(log(sum) * k^n)