task-scheduler.cc

#include <unordered_map>
#include <queue>
#include <vector>
 
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        std::unordered_map<char, int> freq;
        for (char t : tasks) freq[t]++;
 
        // max heap of frequencies
        std::priority_queue<int> pq;
        for (auto& [ch, f] : freq) pq.push(f);
 
        int cycles = 0;
 
        while (!pq.empty()) {
            int cnt = 0;
            std::vector<int> temp;
 
            // run up to n+1 tasks in this cycle
            for (int i = 0; i <= n && !pq.empty(); i++) {
                int f = pq.top(); pq.pop();
                if (f - 1 > 0) temp.push_back(f - 1);
                cnt++;
            }
 
            // push remaining back into heap
            for (int f : temp) pq.push(f);
 
            cycles += pq.empty() ? cnt : (n + 1); // if still tasks left, full cycle
        }
 
        return cycles;
    }
};