30. Task Scheduler with Cooldown and Multiple Machines

Origin: Task Scheduler with Cooldown and Multiple Machines

Given an array tasks and m machines, find the minimum time to complete all tasks. Each time unit can process up to m tasks in parallel. A machine cannot process the same task type again for k time units.

Example 1

Input: tasks = [1, 1, 2, 1], m = 2, k = 2

Output: 3

Explanation:

• Time 1: 2 台机器都跑 type 1 → 剩 [2, 1]
• Time 2: type 1 还在冷却，跑 type 2，另一台空闲 → 剩 [1]
• Time 3: type 1 冷却结束，跑最后一个 type 1 → 总时间 3

Example 2

Input: tasks = [1, 1, 1, 2, 2, 3], m = 3, k = 2

Output: 2

Explanation:

• Time 1: 3 台机器都跑 type 1 → 剩 [2, 2, 3]
• Time 2: 跑 type 2, 2, 3 → 全部完成 → 总时间 2

Input Format

• 第一行：tasks_count（任务数量）
• 第二行：tasks_count 个整数（任务类型数组）
• 第三行：m（机器数量）
• 第四行：k（冷却时间）

Constraints

• 0 <= tasks.length <= 100000
• 0 <= tasks[i] <= 100000
• 1 <= m <= 100000
• 0 <= k <= 100000

Output Format

返回一个整数：完成所有任务的最小时间。

Sample Input 0

1
5
1
0

Sample Output 0

1

Sample Input 1

3
1 2 3
5
2

Sample Output 1

1

---

函数契约

// 输入：tasks（任务类型数组），m（机器数量），k（冷却时间）
// 输出：完成所有任务的最小时间
// 边界：空任务 → 0；m >= 任务数 → 1；k=0 → 无冷却

边界表

场景	返回什么
空任务	0
任务数 <= m 且 k=0	1
单类型多任务	取决于 m 和 k
正常场景	最小时间

Resolution

我的解法（二分查找，O(n log T) AC）

function calculateMinimumTimeUnits(tasks: number[], m: number, k: number): number {
    const n = tasks.length
    if (n === 0) return 0
    if (k === 0) return Math.ceil(n / m)
 
    const freq = new Map<number, number>()
    let maxFreq = 0
    for (const t of tasks) {
        const c = (freq.get(t) ?? 0) + 1
        freq.set(t, c)
        if (c > maxFreq) maxFreq = c
    }
 
    let lo = Math.ceil(n / m)
    let hi = Math.max(lo, (maxFreq - 1) * (k + 1) + n)
 
    const canFinish = (T: number): boolean => {
        if (T * m < n) return false
        const slotsPerMachine = 1 + Math.floor((T - 1) / (k + 1))
        const maxPerType = slotsPerMachine * m
        for (const c of freq.values()) {
            if (c > maxPerType) return false
        }
        return true
    }
 
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2)
        if (canFinish(mid)) hi = mid
        else lo = mid + 1
    }
 
    return lo
}

解题思路

二分查找最小的 T（轮数），用 canFinish(T) 验证 T 轮够不够。

canFinish 的两个条件：

1. T * m >= n：总容量够（T 轮 × m 台机器 >= n 个任务）
2. 每种类型的 count <= m * (1 + floor((T-1)/(k+1)))：单类型不超限

单类型上限怎么算：一台机器在 T 轮内能跑同一类型多少次？第一次在轮 1，之后每隔 k+1 轮能再跑（1 轮跑 + k 轮冷却）。所以是 1 + floor((T-1)/(k+1)) 次，乘以 m 台机器。

为什么间隔是 k+1 不是 k：跑 1 轮 + 冷却 k 轮 = k+1 轮一个周期。题目示例写错了（说 k=2 间隔 1 轮），实际 k=2 间隔 2 轮，正确答案是 4 不是 3。评论区多人确认示例错误。

踩坑经历

1. 题目示例本身是错的：Example 1 说 k=2 时 Time 1 跑完 Time 3 能再跑（间隔 1 轮），但实际 k=2 应该间隔 2 轮，正确答案是 4 不是 3。
2. k 还是 k+1：因为题目示例错误，一开始用 k 作为间隔，实际应该用 k+1。示例的”3”误导了很久。
3. 冷却期间可以跑其他类型：冷却不是”机器不能干活”，是”同一类型不能在这台机器上重复”。冷却期间机器可以跑其他类型的任务。

复杂度

• 时间：O(n log T)，T 是上界，n=100000 足够快
• 空间：O(n)，freq Map

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题型：贪心算法