What is the main pattern behind Task Scheduler?

The core pattern is counting frequencies, then using a greedy frame formula based on the task labels with the highest count. Even though many valid schedules exist, the minimum interval count is controlled by cooldown gaps around the most frequent tasks.

Why is the answer not always just tasks.length?

When repeated high-frequency tasks need long cooldown gaps, there may not be enough other tasks to fill those slots. In that case, idle intervals become mandatory, so the answer grows beyond the raw number of tasks.

Why do we use maxCount in the formula?

If multiple task labels are tied for the highest frequency, they all occupy the final positions of the cooldown frames. Ignoring that tie causes the schedule length to be too small on cases like several letters appearing equally often.

Can Task Scheduler be solved with a heap instead?

Yes. A max heap plus cooldown tracking can simulate the process and is useful when you need the actual order. But for LeetCode 621, the counting formula is simpler and faster because the problem only asks for the minimum number of intervals.

How does the array scanning plus hash lookup pattern fit this problem?

You scan the task array once to build counts with an array or hash lookup, then scan those counts to find the highest frequency and how many labels reach it. That small amount of counting logic replaces a much more expensive interval-by-interval scheduling attempt.

#621

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n 。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个相同种类的任务之间必须有长度为 n 的冷却时间。返回完成所有任务所需要的最短时间间隔。示例 …

数组哈希表贪心排序堆（优先队列）

题目描述

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔 。

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

解释：

在完成任务 A 之后，你必须等待两个间隔。对任务 B 来说也是一样。在第 3 个间隔，A 和 B 都不能完成，所以你需要待命。在第 4 个间隔，由于已经经过了 2 个间隔，你可以再次执行 A 任务。

示例 2：

输入：tasks = ["A","C","A","B","D","B"], n = 1

输出：6

解释：一种可能的序列是：A -> B -> C -> D -> A -> B。

由于冷却间隔为 1，你可以在完成另一个任务后重复执行这个任务。

示例 3：

输入：tasks = ["A","A","A","B","B","B"], n = 3

输出：10

解释：一种可能的序列为：A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B。

只有两种任务类型，A 和 B，需要被 3 个间隔分割。这导致重复执行这些任务的间隔当中有两次待命状态。

提示：

1 <= tasks.length <= 10⁴
tasks[i] 是大写英文字母
0 <= n <= 100

lightbulb

解题思路

方法一：贪心 + 构造

不妨设 $m$ 是任务的个数，统计每种任务出现的次数，记录在数组 cnt 中。

假设出现次数最多的任务为 A，出现次数为 $x$ ，则至少需要 $(x-1)\times(n+1) + 1$ 个时间单位才能安排完所有任务。如果出现次数最多的任务有 $s$ 个，则需要再加上出现次数最多的任务的个数。

答案是 $\max ((x-1) \times(n+1)+s, m)$ 。

时间复杂度 $O(m+|\Sigma|)$ 。其中 $|\Sigma|$ 是任务的种类数。

1

2

3

4

5

6

7

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        cnt = Counter(tasks)
        x = max(cnt.values())
        s = sum(v == x for v in cnt.values())
        return max(len(tasks), (x - 1) * (n + 1) + s)

speed

复杂度分析

指标	值
时间	O(N)
空间	O(26)

psychology

面试官常问的追问

外企场景

question_mark
They want you to stop simulating interval by interval and recognize that the most frequent task controls the schedule length.
question_mark
They are checking whether you can turn cooldown spacing into a counting formula instead of using a heap for every interval.
question_mark
They may ask why the answer is max(total tasks, frame formula), which tests whether you understand when idle slots disappear.

warning

常见陷阱

外企场景

error
Using only the single maximum frequency and forgetting maxCount, which breaks cases where several task labels tie for the top count.
error
Simulating a full schedule with sorting or a heap without noticing that LeetCode 621 has a direct counting solution.
error
Returning the frame formula directly even when many remaining tasks fill all cooldown gaps, causing an overestimate.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solve the same Task Scheduler input with a max heap simulation to show the schedule explicitly instead of only returning its length.
arrow_right_alt
Change the problem so each task label has a different cooldown, which removes the simple closed-form formula.
arrow_right_alt
Ask for the actual task order with idles included, which turns the counting shortcut into a construction problem.

help

常见问题

外企场景

继续练习

#1054 距离相等的条形码 #632 最小区间 #692 前K个高频单词