621.任务调度器

题目来源：https://leetcode-cn.com/problems/task-scheduler/

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

解法

最优贪心算法（构造）

构造法如下：

情景一：

假设tasks = ["A","A","A","A","B","B","B","B","C","C","D"]，n=2

tasks中 A 出现4次，B 出现4次，C和D出现两次，出现字母最多次数m=4，构造m个桶，每个桶的大小为n+1

字母插入桶的顺序依照tasks中字母出现的频率。

先将A插入桶中，结果如下：

接着将B插入桶中，结果如下：

接着将C插入桶中，结果如下：

最后将D插入桶中，结果如下：

此处不将D插入到(4,3)位置，而是将D插入到新的一列中，按照水平方向读取该序列，结果为：ABCDABCABDAB,其长度等于tasks.size()显然这里插入到新列的D与原D之间的间隔永远不会冲突（但必须按照出现次数的顺序插入）。同理，如果接下来还有字母要插入，则沿竖直方向填充桶，最多填充到第(m-1)行的桶，否则开辟新的桶。

情景二：

假设仍与情景一一致，但n变了，tasks = ["A","A","A","A","B","B","B","B","C","C","D","D"]，n=3

tasks中 A 出现4次，B 出现4次，C和D出现两次，出现字母最多次数m=4，构造m个桶，每个桶的大小为n+1

先将A插入桶中，结果如下：

接着将B插入桶中，结果如下：

接着将C插入桶中，结果如下：

接着将D插入桶中，结果如下：

按照水平方向读取该序列，结果为：ABCDABC_ABD_AB，此时该序列长度>tasks.size()，即序列结果并不是tasks序列的一个组合。

由上述两个情景，可以得到如下的结论：

1. 当n->0，tasks.size()->∞，结果为tasks.size()
2. 当n->∞，tasks.size()->0，结果为 (m-1)*(n+1) + cnt，其中m为出现字母次数最多的频数，cnt为出现次数为m的字母数。这里需要加上cnt的原因：最佳的情况是出现次数为m的字母插入到每一个桶中，这就导致第m个桶必须要填充cnt个元素（如情景二所示）。

由此可知，所有任务所需要的最短时间为max{tasks.size(),(m-1)*(n+1) + cnt}.

实现如下（C++）：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int len = tasks.size();
        vector<int> counts(26,0);
        for(char c: tasks){
            counts[c - 'A']++;
        }
        int m=0,m_c=0;
        for(int i=0;i<26;i++){
            if(counts[i]>m){
                m=counts[i];
                m_c = 1;
            }else if(counts[i] == m){
                m_c++;
            }
        }
        return max(len, (m-1)*(n+1)+m_c);
    }
};

复杂度分析：

时间复杂度：O(∣tasks∣+∣Σ∣) 此题∣Σ∣为26

空间复杂度：O(∣Σ∣)