Heaps and Priority Queues
Always take the most urgent thing
A heap plus a waiting area, which is the shape of nearly every scheduling problem.
Key idea
Two collections, not one
Scheduling problems have items that are ready and items that are not ready yet. A heap holds what is available, ordered by urgency. A separate queue holds what is waiting, in the order it becomes available.
Each tick of the clock: move anything that has become available into the heap, then take the most urgent item from the heap. Two structures, one loop.
Why it works
Why taking the most urgent is safe
The greedy choice is to always run whatever is most pressing among the currently available options. For problems where every item takes the same time and delay is what you are minimizing, that is provably optimal by an exchange argument like the one in U6.
It is not automatically right for every scheduling problem. When items have different durations, or when future arrivals change what is best, greedy can fail. Check that the exchange argument holds before assuming it.
Here is a single tick in isolation: two tasks with three runs each, one of them chosen and parked until it is allowed to run again.
Tip
Idle ticks are forced, and the clock still moves
Three of each of two tasks with a gap of two takes 8 ticks: a, b, idle, a, b, idle, a, b. The idle ticks happen because nothing is available yet, and the clock advances anyway.
That is the detail worth building the loop around. Time moves whether or not work happens, so the tick counter has to be advanced before the availability check rather than only when something runs. A loop that skips ahead to the next ready time is a different and more fiddly design.
Why it works
Why waiting is a queue and not a heap
Items enter the waiting area in the order they finish and become available in that same order, because the cooldown is the same for everyone. So the front of a plain queue is always the next to become ready, and no ordering structure is needed.
If cooldowns varied per item, that would stop being true and the waiting area would need to be a heap ordered by ready time. Noticing which of your collections actually needs ordering is worth a sentence in an interview; using a heap where a queue suffices is a small but real signal.
Tip
There is a closed form, and know both
Problems of this exact shape have an arithmetic answer based on the most frequent item and how many share that frequency, computable in one pass with no simulation at all.
The formula is faster and much easier to get subtly wrong, and it does not generalize to variations. Simulate first, then mention that a closed form exists. If you offer only the formula, expect to be asked to justify it.
Predict the output: a max-heap out of a min-heap
heapq only ever gives back the smallest item. The counts here are negated so that the largest one surfaces. Type the three lines it prints.
Task Scheduler
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.