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

class Solution
{
public:
  // int
  // leastInterval (vector<char> &tasks, int n)
  // {
  //   array<int, 26> task_min_next_cycle{};
  //   priority_queue<int, vector<int>, greater<int> > pq;
  //
  //   // n log n
  //   for (char task : tasks)
  //   {
  //     /*
  //      * [0,0]
  //      *
  //      * pq=[A0 B0 - An Bn - A2n B2n]
  //      */
  //     const int task_idx = task - 'A';
  //     pq.push (task_min_next_cycle[task_idx]);
  //     task_min_next_cycle[task_idx] += n + 1;
  //   }
  //
  //   // n log n
  //   int cycle = 0;
  //   while (!pq.empty ())
  //   {
  //     cycle = pq.top ();
  //     do
  //       pq.pop (), ++cycle;
  //     while (!pq.empty () && cycle >= pq.top ());
  //   }
  //
  //   return cycle;
  // }

  int
  leastInterval (vector<char> &tasks, int n)
  {
    /*
["A","A","A","B","B","B"]
2

["A","C","A","B","D","B"]
1

["A","A","A", "B","B","B"]
3

["A","A","A"]
1

["A","A","A","A","A","A","B","C","D","E","F","G"]
1
     */
    array<int, 26> tasks_cnt{};
    vector<int> intervals_task_cnt (tasks.size ());

    // n
    for (char task : tasks)
    {
      const int task_idx = task - 'A';

      intervals_task_cnt[tasks_cnt[task_idx]]++;
      tasks_cnt[task_idx]++;
    }

    int cycle = 0;
    for (int interval = 0;
         interval < intervals_task_cnt.size () && intervals_task_cnt[interval];
         ++interval)
    {
      const int task_cnt = intervals_task_cnt[interval];
      const int interval_cycle = interval * (n + 1);

      // printf ("bef: task_cnt=%d interval=%d cycle=%d interval_cycle=%d\n",
      //         task_cnt, interval, cycle, interval_cycle);

      if (cycle >= interval_cycle)
        cycle += task_cnt;
      else
        cycle = interval_cycle + task_cnt;

      // printf ("aft: task_cnt=%d interval=%d cycle=%d interval_cycle=%d\n\n",
      //         task_cnt, interval, cycle, interval * (n + 1));
    }

    return cycle;
  }
};
39443