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 <= 104tasks[i] 是大写英文字母 ​ n 的取值范围为 [0, 100]

解法

最优贪心算法(构造)

构造法如下:

情景一:

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

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

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

先将A插入桶中,结果如下:

A    
A    
A    
A    

接着将B插入桶中,结果如下:

A B  
A B  
A B  
A B  

接着将C插入桶中,结果如下:

A B C
A B C
A B  
A B  

最后将D插入桶中,结果如下:

A B C D
A B C  
A B D  
A B    

此处不将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次,CD出现两次,出现字母最多次数m=4,构造m个桶,每个桶的大小为n+1

先将A插入桶中,结果如下:

A      
A      
A      
A      

接着将B插入桶中,结果如下:

A B    
A B    
A B    
A B    

接着将C插入桶中,结果如下:

A B C  
A B C  
A B    
A B    

接着将D插入桶中,结果如下:

A B C D
A B C  
A B D  
A B x x

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


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

  1. n->0tasks.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(∣Σ∣)