273. Task Scheduler

Always run the task with the most remaining copies (max-heap). After running it, it must cool down for n intervals before it can return to the heap, so park it in a timed queue.

Greedy: run the most frequent first

Running the busiest task first spreads its copies out best. Each interval:

1. Advance time by 1.
2. If the heap is non-empty, pop the highest count, run one copy (decrement). If copies remain, it can't run again until time + n, so push it into a cooldown queue with that ready time.
3. If the front of the cooldown queue becomes ready at this time, move it back into the heap.

When both the heap and the queue are empty, every task (and any needed idle slot) has been scheduled.

Worked example

tasks = [A,A,A,B,B,B], n = 2: schedule A B idle A B idle A B → 8 intervals.

Complexity

• Time: O(T log 26) ≈ O(T).
• Space: O(26).

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int leastInterval(String[] tasks, int n) {
        Map<String, Integer> counts = new HashMap<>();
        for (String t : tasks) {
            counts.merge(t, 1, Integer::sum);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.addAll(counts.values());

        int time = 0;
        Queue<int[]> cooldown = new LinkedList<>();  // {readyTime, remaining}
        while (!heap.isEmpty() || !cooldown.isEmpty()) {
            time++;
            if (!heap.isEmpty()) {
                int remaining = heap.poll() - 1;
                if (remaining > 0) {
                    cooldown.offer(new int[]{time + n, remaining});
                }
            }
            if (!cooldown.isEmpty() && cooldown.peek()[0] == time) {
                heap.offer(cooldown.poll()[1]);
            }
        }
        return time;
    }
}