文章目录
一、题目
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1：
输入：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：
输入：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
[“A”,“A”,“A”,“B”,“B”,“B”]
[“A”,“B”,“A”,“B”,“A”,“B”]
[“B”,“B”,“B”,“A”,“A”,“A”]
…
诸如此类
示例 3：
输入：tasks = [“A”,“A”,“A”,“A”,“A”,“A”,“B”,“C”,“D”,“E”,“F”,“G”], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/task-scheduler
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路
本题的核心是读懂题意，解题的核心思路是先安排最多次数的任务。
看例子：
输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
思路分析：
执行相同任务中间必须待命单位时间（n）,题目中出现次数最多的是任务A , 所以我就先安排任务A, 然后根据任务A的空隙时间安排其他任务.
# 先那排任务A, 题目中单位时间n = 2
A -> (单位时间:1) -> (单位时间:1) -> A -> (单位时间:1) -> (单位时间:1) -> A
中间间隔的单位时间可以用来安排别的任务，也可以处于“待命”状态。当然，为了使总任务时间最短，我们要尽可能地把单位时间分配给其他任务。现在把任务 B 安排上：
# 在待命时间间隙中安排任务B,得到如下效果:
A -> B -> (单位时间:1) -> A -> B -> (单位时间:1) -> A -> B
很容易观察到，前面两个 A 任务一定会固定跟着 2 个单位时间的间隔。可以将 （AB＋待命时间）看成一个整体，一共有**（A－１）**个整体
最后一个 A 之后是否还有任务跟随取决于是否存在与任务 A 出现次数相同的任务,本题A和B出现次数相同，那么很容易得到如下结论。
(任务 A 出现的次数 - 1) * (n + 1) + (最多次数的任务的个数)，即：
(3 - 1) * (2 + 1) + 2 = 8
思路总结：
- 找到所有任务出现的次数
- 按照任务出现次数进行排序,找出出现次数最多的任务 K
- 计算 sum_time = 时间块 (K-1) X (n+1) + K的个数(是否存在相同次数的任务)
- 比较最小时间和sum_time时间大小
三、代码实例
from typing import List
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
k = len(tasks)
# 考虑边界问题，如果tasks长度为1，则直接返回tasks的长度
if k <= 1:
return k
# 获取各任务出现的次数
tasks_dict = {}
for i in tasks:
if i in tasks_dict:
tasks_dict[i] = tasks_dict[i] + 1
else:
tasks_dict[i] = 1
# 按照出现任务次数进行降序排序，返回任务次数列表
ls = sorted(tasks_dict.values(), reverse=True)
# sum(ls)为理想状态下最小单位时间，即不存在待命时间
# ls.count(ls[0]) 为出现（最多任务次数）的个数
return max(sum(ls), (ls[0]-1)*(n+1)+ls.count(ls[0]))
if __name__ == '__main__':
obj = Solution()
tasks = ["A", "A", "A", "A", "C", "D", "D", "D", "C", "B", "C", "B", "D"]
obj.leastInterval(tasks, n=2)
简化版本：
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
# 1、找出所有字母 出现次数，并按出现次数降序排列
ls = sorted(collections.Counter(tasks).values(), reverse = True)
# 2、找出最大次数, 有几个字母同时出现最大次数
# 3、返回结果
return max( sum(ls), (ls[0] - 1) * (n + 1) + ls.count(ls[0]) )