621. Task Scheduler

這題的題目很不好懂,

我也是看了很多講解, 先了解題目

首先 n的idle到底要怎麼看

我們假設當前的任務是A,他下一次要在執行A就必須idle n次後才能執行

所以這idle的期間,假設可以再放別的任務那再好不過了, 但如果只剩A還沒執行完, 那這空檔就會完全浪費

附上一張花花酱 LeetCode 621. Task Scheduler — 刷题找工作 EP98 的圖

那到底要怎麼去計算呢, 首先我們先統計所有的任務數量, 最大的數字為k, 可以看到A後方一定要放n個idle, 所以其餘的任務可以放進去, p就是最後一次執行的任務, p的數量就是有多少個任務的數量同為k

所以我們總結 所需的數量就是

(k - 1) * (n + 1) + p 

還會有一種case, 就是當任務數量多到就算把idle空間給填滿, 還是不夠放

什麼樣的情況呢, 通常, 因為有idle, 理論上 x個tasks, 用上面公式算出來應該都要大於x, 但是算出來卻小於x的話, 就說明數量太多了, 上面規劃放完仍需其他空間放

所以只須回傳 tasks的 數量即可

花花酱 LeetCode 621. Task Scheduler — 刷题找工作 EP98 圖片來源

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        if(n == 0) return tasks.size();
        unordered_map<char, int> m;
        int maxLen = 0;
        for(int i = 0; i < tasks.size();i++){
            if(m.count(tasks[i])){
                m[tasks[i]]++;
                
            }else{
                m[tasks[i]] = 1;
            }
            maxLen = max(m[tasks[i]], maxLen);
        }
        int p = 0;
        for(auto i: m){
            if(i.second == maxLen){
                p++;
            }
        }
        int res = (maxLen - 1) * (n + 1) + p;
        res = max(res, (int)tasks.size());
        return res;
    }
};