[Day 7] Leetcode 621. Task Scheduler (C++)

前言

今天来分享621. Task Scheduler这一题~ 其实会选到这题本来也是要接续昨天priority queue主题来练习，所以用了top 100 liked的question + heap 的tag之後筛到这一题，结果发现这题也有O(n)的作法，大家都不用priority queue慢慢来XD 所以最後这题最後我是采用比较tricky的方式，不过最後我也会讲一下priority queue的方式的想法是什麽，然後附上别人的code(懒得再写一次了XD)。

想法

解法一: greedy(?)

这题乍看之下会有点没有想法(还是只有我)，但就照一些可能步骤慢慢分析，最後就可以凑出答案了(?)~
首先，省略冗长的题目，其实题目给的task顺序一点都不重要，我们只需要知道 A 任务要做几次，B任务要做几次...，就好了；然後问题就变成说这些任务要怎麽样被好好排列。
那我们第一步先来把题目给的vector简化成这样的次数列表XD

vector<int> cnt(26);
for(int i=0;i<tasks.size();++i){
    cnt[tasks[i]-'A']++;
}

这个cnt的vector代表每个字母的出现次数，cnt[0]储存的就是'A'任务的次数，写法可以参考我们在Day 3提过的char,int隐含转换。
下一步该怎麽办呢？遇到复杂的问题时，我们就要先试着把问题简单化，想想单纯一点的情境XD
如果现在只有一种任务'A'，然後每个A任务间都要间隔n单位时间，那总共就需要(A任务的次数-1) x (n+1) + 1对吧？如现在我们要完成三次A任务，n=2，那最小的排列方式就是 A~~A~~A，总共需要(3-1)x(2+1)+1=7个单位时间，就是以前的国小的种树问题的算法啦XD
那如果现在还有其他任务要完成，例如说B任务要完成2次，C任务要完成1次，我们可以发现都还是7单位时间内可以完成！为什麽？因为B任务跟C任务分别可以插在A任务之间，例如ABCAB~A。那如果B任务要完成4次呢？我们就会发现需要再来一轮！因为我们至少至少需要B~~B~~B~~B才可满足到B的最小间隔让B做完！
结论是，我们可以发现要以任务次数最多的那个任务为准来进行这个基本需时(最高任务的次数-1) x (n+1) + 1的计算！
但你是不是觉得哪里怪怪的，有些情形以上的公式好像会不符合呢？
修改一
第一个，当有好几个任务都需要最高任务次数时，例如A任务要做3次B任务也要做3次，n=2，那我们现在最少就需要AB~AB~AB才能满足这两个任务的最小间隔，可以发现最後面又多了1，想想之後我们就知道要怎麽修改这个公式了：
(最高任务的次数-1) x (n+1) + (最高任务次数的任务数)
修改二
就算这样，是不是还有其他不符合的情况？可以想个一分钟再往下看XD
...
没错，当~~这中间的间隔不够其他任务插入的时候就会不对啦！例如我们前面的举例，现在我们要完成三次A任务，n=2，但我们要完成2次B任务2次C任务2次D任务，那明眼一看我光要完成任务就需要3+2+2+2=9单位时间，怎麽可能7单位时间就完成？这个修改法更简单了，既然我们7单位时间就可以满足间隔的情况，那9单位时间一定可以满足各类间隔，例如说ABCDABCDA，这可能有点不直观，但你可以想想只要最高任务次数的那个任务7个单位时间就可以满足，那其他任务一定有办法有足够间隔的排列进去(好像还是有点抽象，如果想到比较好理解的说法再补上来XD)
所以再多加一条判断如果总任务需时>上面算出的最小间隔需时，那答案就是总任务需时
整个程序码如以下

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        // compute task frequency
        // task 'A' saves to cnt[0]
        vector<int> cnt(26);
        for(int i=0;i<tasks.size();++i){
            cnt[tasks[i]-'A']++;
        }
        // get the max frequency and corresponding tasks counts
        int max_cnt=0;
        int max_tsks=0;
        for(int i=0;i<26;++i){
            //cout<<char(i+'A')<<" "<<cnt[i];
            if(cnt[i]>max_cnt){
                max_tsks=1;
                max_cnt = cnt[i];
            }
            else if(cnt[i]==max_cnt){
                max_tsks++;
            }
        }
        int ans = (max_cnt-1)*(n+1)+(max_tsks);
        return ans>tasks.size()?ans:tasks.size();
    }
};

看起来应该是O(n)时间复杂度内就能完成: 前面先遍历一次O(task.size())+後面扫一次O(26)

解法二: priority queue

priority queue的解法就比较可以想像一点，一样每一轮有n+1的时间，优先要把最多任务次数的任务塞进去，所以就用priority queue的方式把最多任次数的任务依序pop出来，pop出n+1个任务後该轮满了，再把那些有做到的任务们次数-1再塞回去，重复做直到全部任务次数都归0为止~
程序码是取自讨论区的这篇，可以参考：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> counts;
        for (char t : tasks) {
            counts[t]++;
        }
        priority_queue<int> pq;
        for (pair<char, int> count : counts) {
            pq.push(count.second);
        }
        int alltime = 0;
        int cycle = n + 1;
        while (!pq.empty()) {
            int time = 0;
            vector<int> tmp;
            for (int i = 0; i < cycle; i++) {
                if (!pq.empty()) {
                    tmp.push_back(pq.top());
                    pq.pop();
                    time++;
                }
            }
            for (int cnt : tmp) {
                if (--cnt) {
                    pq.push(cnt);
                }
            }
            alltime += !pq.empty() ? cycle : time;
        }
        return alltime;
    }
};

结语

才第7天就快没梗了QAQ