題目網址：https://leetcode.cn/problems/task-scheduler/

題意：給一 char array tasks 代表 CPU 須執行的任務 list, 其中每個字母代表一種不同種類的任務, 任務能以任意順序執行, 且每個任務皆可在 1 個單位時間內完成。在任意一個時間單位, CPU 可以選擇完成一個任務 or 處於待命狀態。

然而, 在兩個相同種類的任務之間必須有長度為 n 的冷卻時間。

計算並返回完成所有任務的最短時間。

注意：tasks[i] 必為大寫字母。

Solution 1：

想法：利用 Greedy + Heap, 應該處理的出現次數最多的 task, 盡量讓每一輪都能塞滿 n + 1 個 task（因為題目要求最短時間）。盡量先取高頻的 task, 然後再來取低頻的 task, 理由如下：

若改成優先取那些低頻的 task, 可能會讓低頻的 task 一下就被取完, 導致剩下的 task 整體的多樣性減少。當 max heap 中的 task 種類 < n + 1, 但每一輪又要取 n + 1 個時, 就會需要使用 idle 來填補每一輪中剩餘的 task ➔ 這無法滿足題目要求的最短時間

  • 每次從 max heap 中取出 n + 1 個不同種類的 task
  • 若無法從 max heap 取出 n + 1 個 task, 分成兩種情況：
    • 非最後一輪, 用 idle 填滿剩餘的 task
    • 為最後一輪, 則不需用 idle 填滿剩餘的 task（因為沒有下一輪）
  • 將取出的 task 之 cnt -= 1, 若 cnt > 0, 則 push 回 max heap 中
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> freqs;
        for (const auto& ch : tasks) {
            freqs[ch]++;
        }

        priority_queue<int> pq; // max heap
        for (const auto& [ch, num] : freqs) {
            pq.emplace(num);
        }

        int res = 0;
        while (!pq.empty()) {
            vector<int> bucket; // 用來暫存這一輪取出的 task 之 cnt - 1
            const int num = min(n + 1, int(pq.size())); // 紀錄這一輪取出的 task 個數

            // 一次從 max heap 中取 num 個 task 放入桶子中, 取出記得 cnt 要減 1
            for (int i = 0; i < num; ++i) {
                bucket.emplace_back(pq.top() - 1); // 紀錄 cnt - 1
                pq.pop();
            }

            // 若取出的 task 之 cnt > 0, 則 push 回 max heap 中
            for (const auto& cnt : bucket) {
                if (cnt > 0) {
                    pq.emplace(cnt);
                }
            }

            // 若 max heap 不為空, 則代表還有下一輪, 那這一輪的桶會是全填滿的狀態
            // 否則, 代表這一輪為最後一輪, 且桶中個數為 num 個(可能不滿 n + 1 個)
            res += (pq.empty() ? num : n + 1);
        }
        return res;
    }
};
  • time：$O(len)$ ➔ $O(len) + O(len \cdot log(26))$
    • $O(len)$：遍歷 tasks 每個 char
    • $O(len \cdot log(26))$：每一次從 pq 中取 n + 1 個數放入桶子中, 總共取 len 個, 故 pq 要調整 len 次 , 而 pq 中最多 26 個數
  • space：$O(1)$ ➔ 只需常數空間, 因為 freqs 只需 $O(26)$, 且 bucket 和 pq 最多 $O(26)$

Solution 2：

想法：利用 Greedy, 假設今天只有一種任務 A, tasks = ['A', 'A', 'A'] 且 n = 2, 則最小排列方式為 A _ _ A _ _ A, 其中 A _ _ 可看作是一個桶子（長度為 n + 1）, 總共需花費 (3 - 1) x (2 + 1) + 1 = 7 個時間單位, 也就是 (頻率最高任務的次數 - 1) x (n + 1) + 1, 但會有以下情況不適用：

  • 當頻率最高任務次數的任務數不只一個時
    e.g. tasks = ['A', 'A', 'A', 'B', 'B', 'B'], n = 2
    最小排列方式為 A B _ A B _ A B, 總共需花費 (3 - 1) x (2 + 1) + 2 = 8
    ➔ 公式需修改為 (頻率最高任務的次數 - 1) x (n + 1) + (頻率最高任務次數的任務數)

  • 當中間的間隔不夠其他任務插入時
    e.g. tasks = ['A', 'A', 'A', 'B', 'B', 'C', 'C', 'D', 'D'], n = 2
    按照上述公式會得出需花費 (3 - 1) x (2 + 1) + 1 = 7
    但總共有 9 個任務, 根本不可能在 7 個時間單位內完成
    我們可以在間隔 _ _ 後加上其他任務, 因此最小排列方式為 A B C D A B C D A
    ➔ 如果 任務個數 > 公式算出的最少時間, 則答案為任務個數

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> freqs(26, 0);
        for (const auto& ch : tasks) {
            freqs[ch - 'A']++;
        }

        // 取出現次數最多的 char (最高任務的次數)
        const int maxFreq = *max_element(freqs.begin(), freqs.end());

        // 出現次數為 maxVal 的個數
        int maxCnt = 0;
        for (const auto& num : freqs) {
            if (num == maxFreq) {
                maxCnt++;
            }
        }

        return max((maxFreq - 1) * (n + 1) + maxCnt, tasks.size());
    }
};
  • time：$O(len)$ ➔ 遍歷 tasks
  • space：$O(1)$ ➔ freqs