621

public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        var freq = new Dictionary<char, int>();
        foreach (char t in tasks)
            freq[t] = freq.GetValueOrDefault(t) + 1;           // count how many times each task appears
 
        var pq = new PriorityQueue<int, int>(
            freq.Values.Select(c => (c, c)),
            Comparer<int>.Create((a, b) => b.CompareTo(a)));   // max-heap of counts (heapify, O(u))
 
        int time = 0;
 
        while (pq.Count > 0) {                                  // one round per iteration, until no work is left
            var survivors = new List<int>();                    // holding area: tasks that still have work after this round
            int popped = 0;                                     // distinct tasks actually run this round
 
            for (int i = 0; i <= n && pq.Count > 0; i++) {      // up to n + 1 slots; stop early if no tasks left to pick
                int count = pq.Dequeue();                       // greedy: take the task with the most remaining work
                popped++;                                       // that task takes one slot
                if (count > 1) survivors.Add(count - 1);        // ran once; if work remains, hold it back for the next round
            }
 
            foreach (int c in survivors)
                pq.Enqueue(c, c);                               // return survivors only after the round, so no task repeats within n + 1 slots
 
            time += pq.Count == 0 ? popped : n + 1;             // heap empty: this was the last round, count only the tasks run (no trailing idles)
                                                                // heap not empty: more rounds follow, so this round must last n + 1 slots; pad the unused ones with idles
        }
 
        return time;
    }
}

Little tricky about adding survivors back, and counting the time.

---

Actually there is a closed form for this problem.

public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        var freq = new Dictionary<char, int>();
        foreach (char t in tasks)
            freq[t] = freq.GetValueOrDefault(t) + 1;
 
        var maxFreq = freq.Values.Max();
        var maxCount = freq.Values.Count(f => f == maxFreq);
 
        return Math.Max((maxFreq - 1) * (n + 1) + maxCount, tasks.Length);
    }
}

Consider the task with the highest frequency. Surely it dominates the structure. We would like to schedule it earlier than lesser priority tasks. Because if we don’t, it may end up at the end, and that would mean too many idles needed.

So, let’s ‘put’ this task at certain places. We can say we have slots of n+1 size, and we put this task on first position of these. So, if there are no other tasks of this freq, by the end of second last slot, all tasks would have been completed. But if there are some with same max freq as our main task, then we need to schedule them in the last round as well.

Overall, we need maxFreq - 1 slots of n+1 size, PLUS, the last slot (which is basically of maxCount size, basically all the tasks with the maxFreq).

This should be the total time needed. BUT, in case the n is smaller, and we have remaining tasks at each slots we made, then the total time would be tasks.Length, as no idle time is needed and all tasks must be scheduled.

In other words,

• The most frequent task (freq = maxFreq) dominates. Schedule it first in each window, or it ends up at the end and forces idles.
• It needs maxFreq - 1 full windows of size n + 1, then a final partial window.
• The final window holds only the tasks that tie at maxFreq (maxCount of them).
• Lower-frequency tasks fill the idle gaps inside the earlier windows.
• Skeleton time = (maxFreq - 1) * (n + 1) + maxCount
• If the other tasks overflow the gaps (small n, many tasks), windows stretch, there are no idles, and time = tasks.Length.
• Answer = Math.Max(tasks.Length, (maxFreq - 1) * (n + 1) + maxCount)