<p>You are given an array of CPU <code>tasks</code>, each represented by letters&nbsp;A&nbsp;to Z, and a cooling time, <code>n</code>. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there&#39;s a constraint: <strong>identical</strong> tasks must be separated by at least <code>n</code> intervals due to cooling time.</p>

<p>​Return the <em>minimum number of intervals</em> required to complete all tasks.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block" style="
    border-color: var(--border-tertiary);
    border-left-width: 2px;
    color: var(--text-secondary);
    font-size: .875rem;
    margin-bottom: 1rem;
    margin-top: 1rem;
    overflow: visible;
    padding-left: 1rem;
">
<p><strong>Input:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
">tasks = [&quot;A&quot;,&quot;A&quot;,&quot;A&quot;,&quot;B&quot;,&quot;B&quot;,&quot;B&quot;], n = 2</span></p>

<p><strong>Output:</strong> <span class="example-io" style="
font-family: Menlo,sans-serif;
font-size: 0.85rem;
">8</span></p>

<p><strong>Explanation:</strong> A possible sequence is: A -&gt; B -&gt; idle -&gt; A -&gt; B -&gt; idle -&gt; A -&gt; B.</p>

<p>After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3<sup>rd</sup> interval, neither A nor B can be done, so you idle. By the 4<sup>th</sup> cycle, you can do A again as 2 intervals have passed.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block" style="
    border-color: var(--border-tertiary);
    border-left-width: 2px;
    color: var(--text-secondary);
    font-size: .875rem;
    margin-bottom: 1rem;
    margin-top: 1rem;
    overflow: visible;
    padding-left: 1rem;
">
<p><strong>Input:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
">tasks = [&quot;A&quot;,&quot;C&quot;,&quot;A&quot;,&quot;B&quot;,&quot;D&quot;,&quot;B&quot;], n = 1</span></p>

<p><strong>Output:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
">6</span></p>

<p><strong>Explanation:</strong> A possible sequence is: A -&gt; B -&gt; C -&gt; D -&gt; A -&gt; B.</p>

<p>With a cooling interval of 1, you can repeat a task after just one other task.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block" style="
    border-color: var(--border-tertiary);
    border-left-width: 2px;
    color: var(--text-secondary);
    font-size: .875rem;
    margin-bottom: 1rem;
    margin-top: 1rem;
    overflow: visible;
    padding-left: 1rem;
">
<p><strong>Input:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
">tasks = [&quot;A&quot;,&quot;A&quot;,&quot;A&quot;, &quot;B&quot;,&quot;B&quot;,&quot;B&quot;], n = 3</span></p>

<p><strong>Output:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
">10</span></p>

<p><strong>Explanation:</strong> A possible sequence is: A -&gt; B -&gt; idle -&gt; idle -&gt; A -&gt; B -&gt; idle -&gt; idle -&gt; A -&gt; B.</p>

<p>There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tasks.length &lt;= 10<sup>4</sup></code></li>
	<li><code>tasks[i]</code> is an uppercase English letter.</li>
	<li><code>0 &lt;= n &lt;= 100</code></li>
</ul>

std::unordered_map<char, int> charFreqMap {};

class Compare {
public:
    bool operator()(char a, char b) {
        return charFreqMap[a] < charFreqMap[b];
    }
};

class Solution {
private:
    std::priority_queue<char, std::vector<char>, Compare> max_PQ;
    void printMap() {
        char key;
        for (auto p : charFreqMap) {
            char key = p.first;
            std::cout << key << ": " << charFreqMap[key] << '\n';
        }
        std::cout << '\n';
    }

public:
    int leastInterval(vector<char>& tasks, int n) {        
        int ans = 0;
        int cycle = n+1;

        for (char t : tasks) {
            if (charFreqMap.contains(t)) {
                charFreqMap[t] += 1;
            } else {
                charFreqMap[t] = 1;
            }
        }

        // UGH
        // for (char t : tasks) {
        //     max_PQ.push(t);
        // }

        for (auto p : charFreqMap) {
            max_PQ.push(p.first);
        }

        std::unordered_set<char> used {};
        while (!charFreqMap.empty()) { // HMM
            // Populate a cycle
            // Review radius arg
            cycle = n+1;
            used.clear();

            while (cycle > 0 && !max_PQ.empty()) {
                char cache = max_PQ.top();
                if (charFreqMap[cache] == 1) {
                    charFreqMap.erase(cache);
                } else {
                    charFreqMap[cache] -= 1; // WARNING: this can recreate elements if you don't check for membership...
                    used.insert(cache);
                }
                max_PQ.pop();
                cycle -= 1;
            }

            for (char u : used) {
                max_PQ.push(u);
            }

            if (max_PQ.empty()) {
                ans += n+1 - cycle;
            } else {
                ans += n+1; // populate remaining elems in cycle with idles
            }
        }

        return ans;
    }
};
49656