Tasks are letters, each taking one interval. The same task needs at least n intervals between two runs; the CPU may idle. Return the least number of intervals to finish every task.
Before you code
Running the task with the most copies left first leaves the fewest idle gaps. A max-heap of counts picks it, and a queue holds tasks that are cooling down.
Hints
- Count tasks; push the counts into a max-heap.
- Each interval: pop the largest count, run it, and if copies remain, put
(count - 1, ready_time)in a cooldown queue. - Move tasks whose ready time has come back into the heap.
- A closed-form answer also exists:
max(len(tasks), (max_count - 1) * (n + 1) + number_of_tasks_with_max_count).
Production & complexity notes
When solving Task scheduler on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Top-k and merging streams to reinforce the underlying pattern.
What it practices
A priority queue driving a schedule, from Top-k and merging streams.