621. Task Scheduler.md

621. Task Scheduler

思路

思路一、暴力模拟

首先应该明确我们始终应该优先处理出现次数最多的任务。为此我们可以模拟这个过程，先统计每个字母的次数，然后将这些次数送入到一个优先队列（最大堆）里，然后每一轮都从优先队列里面取n+1个元素出来将其次数减一，不断重复这个过程直到队列空。

设任务总数为N，不同的任务数为M（M<=26），那么时间复杂度为O(NlogM)，空间复杂度为O(M)。亲测此方法500ms左右，效率较低。

思路二

还是按照优先处理出现次数最多的任务这个原则。我们假设 A 为出现次数最多的任务，假设其出现了 p 次，考虑到冷却时间，那么执行完所有任务的时间至少为 (p - 1) * (n + 1) + 1，如下左图所示，其中浅色代表空闲时间。

然后我们应当考虑把剩余的任务安排到这些空闲时间里，先将这些任务的出现次序，从大到小进行安排，会有下面两种情况：

• 某个任务和 A 出现的次数相同，例如图 2 中的任务 B。此时我们只能让 B 占据 p - 1 个空闲时间，而在非空闲时间里额外安排一个时间给 B 执行；
• 某个任务比 A 出现的次数少，例如图 2 中的任务 C 和 D。此时我们可以按照列优先的顺序，将其填入空闲时间中。

如果在安排某一个任务时，遇到了剩余的空闲时间不够的情况，那么答案一定就等于任务的总数。这是因为我们可以将空闲时间增加虚拟的一列，继续安排任务。

所以我们只需要求出出现次数最大（设为mx）的任务A，以及出现次数和A同样多的任务（即B这种）数mx_cnt，这样最终结果就为max(N, (n + 1) * (mx - 1) + mx_cnt)，其中N为任务总数。

空间复杂度O(1)，时间复杂度O(N)

参考来源

C++

思路一

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        if(n == 0) return tasks.size();
        vector<int>cnt(26, 0);
        for(char t: tasks) cnt[t - 'A']++;
         
        priority_queue<int>maxheap;
        for(int i: cnt) if(i > 0) maxheap.push(i);
        
        int res = 0;
        while(!maxheap.empty()){
            vector<int>tmp; // 存放从maxheap取出的元素
            for(int i = 0; i <= n; i++){
                if(maxheap.empty()) {
                    if(!tmp.empty()) res += n + 1 - i; // idle
                    break;
                }
                res += 1;
                auto num = maxheap.top(); maxheap.pop();
                if(--num > 0) tmp.push_back(num);
            }
            
            for(auto a: tmp) maxheap.push(a); // 放回队列中
        }
        
        return res;
    }
};

思路二

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int>cnt(26, 0);
        for(char t: tasks) cnt[t - 'A']++;
        
        int mx = cnt[0], mx_cnt = 0;
        for(int i: cnt) mx = max(mx, i);
        for(int i: cnt) if(i == mx) mx_cnt++;
        
        return max((int)tasks.size(), (n + 1) * (mx - 1) + mx_cnt);
    }
};