题目描述

给你一个用字符数组 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 任务。

算法思路

这道题目一开始我是想纯模拟+贪心做的，思路差不多是这样的：

  1. 统计每个任务出现的次数，然后进行排序得到hash_map；
  2. 假定我们得到的tasks队列是这样的：["A": 3, "B": 3, "C": 2, "D": 1], n=2
  3. 我们先把最大的排好:A X X A X X A X X，可以看出空出来了6个位置，那么这六个位置对于剩下的字母，只要总数量小于等于6，那么一定可以放下：A B C A B C A B D，因为我们是以一种贪心的思路进行的：始终把最多次数的任务排开，其他的任务插空即可。
  4. 但是模拟到这出了些问题，因为我们这个示例给的比较好，万一插不满空呢：["A": 2, "B": 1], n=2，得到：A B X A X X，最后这两个X什么时候删呢？因为我们能看到样例，所以知道A B X A即可。["A": 2, "B": 2]，那如果再是["A": 2, "B": 2]，得到A B X A B X，此时同样只剩两个字母B，又只需要删除1个字母。

所以最后还是没模拟出来，看来一个大神题解。

借鉴思路

  1. 还是跟上面排序，然后对出现次数最多的任务展开：A X X A X X A，但是我们此时只需要保持这个任务能做完即可，也就是最后两个X不需要了，此时时间为min_len = (COUNT_A - 1) * (n + 1) + 1 = 7。
  2. 然后遍历其他的任务T，如果T的次数和A一样，那么时间min_len需要+1，因为此时出现了A T X A T X A T，也就是仅凭X占位符无法把T运行完；如果T2的此时小于A，那么时间不需要改变，因为能插进去得到A T T2 A T T2 A T
  3. 接下来是最重要的一点，此时发现没有占位符了，如果再出现[“T3”: 2]，该怎么排列？答案是直接接着T2后面排即可，因为A与A之间的差值已经是2了，再往后排只会更大，肯定满足冷却期，比如：A T T2 T3 A T T2 T3 A T，并且此时注意到有，时间就是任务序列长度，因为所有任务都紧邻。
  4. 所以总的时间就是：如果还有空闲位置，那么就是我们设计的长度min_len，否则就是任务序列长度task_len

得到代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> hash_map(26, 0);
        for (auto c : tasks) {
            hash_map[c - 'A'] ++;
        }
        sort(hash_map.begin(), hash_map.end());
        // A X X A X X A
        // (2 + 1) * (3 - 1) + 1
        int minlen = (n + 1) * (hash_map[25] - 1) + 1;
        for (int i = 24; i >= 0; i--) {
            if (hash_map[i] == hash_map[25]) ++minlen;
        }
        return max(minlen, int(tasks.size()));
    }
};