题目描述
给你一个用字符数组 tasks
表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间,CPU 可以完成一个任务,或者处于待命状态。
然而,两个 相同种类 的任务之间必须有长度为整数 n
的冷却时间,因此至少有连续 n
个单位时间内 CPU 在执行不同的任务,或者在待命状态。
你需要计算完成所有任务所需要的 最短时间。
样例
输入:tasks = ["A","A","A","B","B","B"], n = 2
输出:8
解释:A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
提示
- 任务的总个数为
[1, 10000]
。 n
的取值范围为[0, 100]
。
算法
(贪心,堆 / 优先队列) $O(m)$
- 统计出每个字母的出现次数,然后把出现次数的大于 0 的次数放入大根堆中。堆中最多有 26 个元素。
- 贪心策略如下:我们按
n + 1
个时间一组来安排任务,重复次数多的任务优先安排。每次从堆中最多取出前n + 1
个元素,然后这些元素减 1,如果元素仍然大于 0,则放回堆中。每组的时间为n + 1
,如果这是最后一组(即没有再往堆中放回),则这一组的时间为取出的元素个数。
时间复杂度
- 假设总共有 $m$ 个字母,则堆中元素的和每次至少减少 $n + 1$,由于元素个数为常数个,则操作堆的时间可以近似为常数,故总时间复杂度为 $O(m)$。
空间复杂度
- 堆的空间为常数,所以可以近似为常数的空间。
C++ 代码
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> cnt(26, 0);
for (char t : tasks)
cnt[t - 'A']++;
priority_queue<int> q;
for (int i = 0; i < 26; i++)
if (cnt[i] > 0)
q.push(cnt[i]);
int ans = 0;
while (1) {
vector<int> tmp;
for (int i = 1; i <= n + 1; i++)
if (!q.empty()) {
tmp.push_back(q.top() - 1);
q.pop();
}
for (int t : tmp)
if (t > 0)
q.push(t);
if (q.empty()) {
ans += tmp.size();
break;
} else {
ans += n + 1;
}
}
return ans;
}
};
思路很简单易懂
思路碉堡了
如果堆内元素种类是固定的话,时间复杂度就可以看作是常数嘛?感觉是比较慢的O(n)
这道题时间复杂度与 $n$ 无关,只与 $m$ 有关,操作堆的时间复杂度总是 $\log 26$。用大 $O$ 表示时间复杂度的时候,一般会忽略常数。