Task Scheduler
你有一个由大写字母组成的字符串 tasks，每个任务对应一个字母，还有一个整数 n。处理器每个时间单位运行一个任务，任务顺序由你决定，也可以空闲一个时间单位。
同一个字母的两次运行之间至少需要间隔 n 个时间单位：一个字母在时间单位 t 运行后，最早可以在时间单位 t+n+1 再次运行。请返回运行完所有任务所需的最少时间单位数。
函数
- tasksstring
- 这些任务，每个任务对应一个大写字母
- ninteger
- 同一个字母的两段连续序列之间的最少单位数
- 返回值integer
- 最少的单位数量，包括空闲的单位
约束条件
1 ≤ tasks.length ≤ 104tasks中只包含大写字母A到Z。0 ≤ n ≤ 100
示例
- 输入
- tasks = "CACBAC"n = 2
- 输出
- 7
- 解释
- C 运行 3 次，每次运行之间间隔 2 个单位，因此仅 C 的运行就占用 7 个单位。顺序为
C A B C A、空闲、C，用 A 和 B 填补间隔，只需要 1 个空闲单位：7。
- 输入
- tasks = "ABCABD"n = 1
- 输出
- 6
- 解释
- A 和 B 各运行两次，两次运行之间间隔一个单位。顺序
A B C A B D能让它们彼此分开，且没有任何空闲单位，所以答案是任务数量6。
- 输入
- tasks = "ZZZ"n = 3
- 输出
- 9
- 解释
- 只有 Z 需要运行，所以每个间隔都是空闲的：Z，三个空闲单位，Z，三个空闲单位，Z。一共是
9个单位。
进阶
你还能返回一个长度最短的时间表吗？用字符串表示，每个空闲单元用一个 . 表示。
提示
逐个打开提示，每个都会多透露一点。
哪个字母会让空闲时间变得不可避免？想一想出现频率最高的字母，以及它的各次出现之间必须间隔多远。
先放出现频率最高的字母：一段字符、
n个空位、另一段字符，以此类推。这样需要多少个单位？空位里可以放什么？其中，
top是最高的计数，atTop是具有该计数的字母数量，所需帧数为(top-1) × (n+1) + atTop个单位。将这个数与任务数量进行比较。
题解
顺序由你决定，所以问题是你最少需要多少个空闲单位。出现次数最多的字母决定了这一点：它的各次运行之间必须间隔 n+1 个单位，其他任务则填补它们之间的空隙。你可以用最大堆优先安排出现次数最多的字母，也可以用一个公式直接计算空隙数量。
使用最大堆模拟回合
思路
把时间划分为长度为 n+1 个单位的轮次。每个字母在一轮中最多运行一次；某个字母在一轮的某个位置运行后，可以在下一轮的相同位置再次运行，间隔正好是 n+1 个单位。在每一轮中，先运行剩余次数最多的字母。它们剩余的运行次数必须间隔 n+1 个单位，因此它们可能导致末尾出现空闲时间；先运行它们可以让剩余次数保持均衡。
只要还有任务未完成，一轮就耗时 n+1 个单位，空出的时隙计为空闲时间；最后一轮只耗费其中运行的任务所需的时间。在示例 1 中，各轮依次运行 C、A、B，然后运行 C、A 并空闲 1 个单位，最后一轮只运行 C：3 + 3 + 1 = 7。每次弹出都会运行一个任务，因此有 m 个任务和 k ≤ 26 个字母时，时间复杂度为 O(m log k)。
算法
- 统计每个字母的出现次数，并将大于零的次数放入最大堆。
- 当堆不为空时，运行一轮：弹出最多
n+1个次数，并保留减一后仍大于零的次数。 - 将保留的次数放回堆中。
- 如果堆不为空，时间增加
n+1；否则，时间增加本轮运行的任务数。 - 返回时间。
import heapq
from collections import Counter
def leastInterval(tasks, n):
# heapq is a min-heap, so store negated counts to pop the largest first.
heap = [-c for c in Counter(tasks).values()]
heapq.heapify(heap)
time = 0
while heap:
# One round of n+1 slots: run the most frequent tasks left, each at most once.
left = []
ran = 0
while ran < n + 1 and heap:
c = -heapq.heappop(heap)
ran += 1
if c > 1:
left.append(c - 1)
for c in left:
heapq.heappush(heap, -c)
# A round lasts n+1 units, idle included; the last one ends with its last task.
time += n + 1 if heap else ran
return time统计出现频率最高的字母的帧数
思路
设 top 是最高出现次数，由字母 X 持有。在 X 的每组连续出现后，除了最后一组，都留出 n 个空位：先放置 top-1 个长度为 n+1 的时间段，再放置 X 最后一组。出现次数少于 top 的字母可以填入空位，每个时间段放一个副本，因此它们的副本之间至少相隔 n+1 个单位。其他每个出现 top 次的字母会在末尾增加一个单位。出现次数达到最高值的字母有 atTop 个，因此总长度为 (top-1) × (n+1) + atTop 个单位。
没有任何调度方案能更短：将前 (top-1) × (n+1) 个单位分成 top-1 个长度为 n+1 的时间窗口。每个最高频字母在每个窗口中最多出现一次，因此这 atTop 个字母在这些窗口之后都还剩下一组。若任务数量超过空位数量，就让一些时间段延长到超过 n+1。更长的时间段只会扩大间隔，因此不会有空闲时间，答案就是 m。答案取两者中的较大值。
算法
- 统计 26 个字母各自出现的次数。
- 找出最高次数
top，以及达到这个次数的字母数atTop。 - 计算
frames = (top-1) × (n+1) + atTop。 - 返回
frames和任务数量中较大的值。
def leastInterval(tasks, n):
counts = [0] * 26
for ch in tasks:
counts[ord(ch) - ord("A")] += 1
top = max(counts)
at_top = counts.count(top) # tasks that share the highest count
# top-1 full frames of n+1 units, then one last slot per task at the top count.
frames = (top - 1) * (n + 1) + at_top
# With more tasks than frame slots, no idle unit is needed at all.
return max(frames, len(tasks))
易错点和边界情况
- 忘记计算并列最多的字母。在
"MMNNPP"中，n = 5，三个字母的出现次数都是 2，所以答案是(2-1) × 6 + 3 = 9，而不是 7。 - 忘记取较大值。在示例 2 中，任务帧的计算结果是
(2-1) × 2 + 2 = 4，但 6 个任务需要 6 个时间单位。 - 给最后一轮也计算完整的
n+1个时间单位。最后一个任务之后没有等待时间：示例 3 的结果会是 12，而不是 9。 - 在一轮中途把计数放回去。这样，同一个字母就可能在这一轮中再次被取出，导致两次运行之间的间隔太短。
常见问题3
任务调度器的时间复杂度是多少？
统计字母需要 O(m) 的时间，其中有 m 个任务。公式随后会读取 26 个计数，因此答案的时间复杂度为 O(m)，额外空间复杂度为 O(1)。最大堆模拟每个任务都会弹出一次，时间复杂度为 O(m log k)，其中字母数 k ≤ 26。
任务计划程序什么时候不需要空闲时间？
当 m ≥ (top-1) × (n+1) + atTop 时，任务会填满所有空位并拉伸框架，而不是留下空隙，所以答案是 m。示例 2 中，"ABCABD" 在 n = 1 时就是这种情况。
输入字符串的顺序重要吗？
不。任务的运行顺序由你决定，所以重要的只有每个字母出现的次数。"CACBAC" 和 "CCCAAB" 在 n = 2 时都需要 7 个单位。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def leastInterval(tasks, n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tasks = "CACBAC" n = 2
预期输出
7