链接: https://leetcode-cn.com/problems/task-scheduler/
题意
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。两个相同种类的任务之间必须有长度为整数 n 的冷却时间,计算完成所有任务所需要的最短时间 。
解法
一开始考虑模拟,然后发现情况不对
实现起来有点复杂
对于策略也不是很确定
看了题解才明白了这道题的奥义
考虑对最多任务数量的任务A建立桶,并且在这个桶中A是第一个任务
后面可以依次安排任务数量次多的任务B,C
剩下一些任务数量少的可以进行插空安排,如果是冷却时间内则不会产生时间上的影响
最后的结果是只需要算两个数
- 记录最大任务数量$N$,看一下任务数量并列最多的任务有多少个,即最后一个桶子的任务数$X$,计算 $NUM_1=(N-1)*(n+1)+x$
- 所有的任务数量$NUM_2$,取两者的较大值即为答案
代码
1 | class Solution { |