<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>

from collections import Counter
from heapq import heappush, heappop, heapify

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Observe that that max freq task(s) would dictate the number of cycles required.
        # The lower freq tasks can be just scheduled along with the max freq task
        # within a time slot (n + 1). However, what if we have multiple tasks with max freq?
        # Those tasks can be scheduled within the last cycle. This calculation assumes that
        # there is idle time needed for some time slots. If there is no idle time in which lower
        # freq task can be scheduled continuously one after another, the len(tasks) would be 
        # the answer 

        task_freq = Counter(tasks)
        max_freq = max(task_freq.values())

        # Time slots (-1 the last slot)
        time_slots = (max_freq - 1) * (n + 1)

        # tasks with max_freq
        max_freq_tasks = sum([max_freq == count for count in task_freq.values()])
        
        # Plus the cycles in the last slot
        time_slots = time_slots + max_freq_tasks

        return max(time_slots, len(tasks))



    
    def leastInterval_v0(self, tasks: List[str], n: int) -> int:
        # Prioritize processing the most frequent tasks first
        # Use a max heap to keep most freq tasks
        # Pop from the heap for the number of tasks in a slot size (n + 1)
        # Decrease count (actual increase for maxHeap) if count <= -1
        # Once count reach 1, meaning we don't add the task to queue anymore
        # Number of intervals can be accumulated with each non-empty queue scheduling 
        # On the last intervals, when the queue is empty, number of intervals
        # is just the items left in the queue

        max_heap = []

        task_freq = Counter(tasks)
        for task, count in task_freq.items():
            heappush(max_heap, (-count, task))

        cycles = 0

        while max_heap:
            queue = []

            # start scheduling for one cycle (n-interval)
            for _ in range(n + 1):  # inclusive the task (1) + n
                if max_heap:
                    queue.append(heappop(max_heap))
            
            # decrease task count until 1, which will be scheduled in the last cycle
            for count, task in queue:
                if count < -1:
                    heappush(max_heap, (count + 1, task))

            cycles += (n + 1) if max_heap else len(queue)


        return cycles



17100