前言

今天來分享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