Task scheduler with cooldown in Python

Why it matters

A server has one worker. You hand it a list of jobs. Some jobs are of the same kind, and a rule says that two jobs of the same kind must have a gap between them. For example, the same API may allow only one call every few seconds, so the worker must do other work in between. The question is simple to state: what is the shortest total time that finishes all jobs and respects the gap?

This problem shows up in scheduling, rate limiting, and in many interview questions. It also shows a clear use of a heap. A heap answers "which item is the most urgent right now?" quickly. Here, the most urgent task is the one with the most work left, because it is the hardest to fit in later.

In this lesson you learn to count the tasks, derive a formula for the minimum time, and then build the actual schedule with a heap and a cooldown queue. The first lesson of this module covers the heap rules. The code below uses Python's heapq module, which keeps a heap inside a normal list.

The problem in plain words

You are given a list of tasks. Each task is a single letter, such as A or B. The same letter can appear many times. You have one worker, and the worker does one task per time unit. A time unit is called a slot. Some slots can be idle, meaning the worker waits and does nothing.

There is one rule. After a task runs, the same task cannot run again until at least n other slots have passed. The number n is called the cooldown. If n is 2, then the task A at slot 1 can run again no earlier than slot 4. Slots 2 and 3 must be used by something else or left idle.

The goal is to find the smallest number of slots that finishes every task while obeying the cooldown.

Here is a small example. Tasks are AAABBB and the cooldown n is 2. One valid schedule is:

slot:   1 2 3 4 5 6 7 8
task:   A B - A B - A B

The dash means an idle slot. The schedule takes 8 slots. Check the rule for A: it runs at slots 1, 4, and 7. The gap between two runs is 3, which is n + 1, so the rule holds. The same check works for B: slots 2, 5, and 8.

Could it be shorter? Put a faster order in and see what happens. The heap and the formula in the next sections show that 8 is the best answer for this input.

Start by counting

Count how many times each task appears. In Python, collections.Counter does this in one line. A Counter is a dictionary that maps each item to the number of times it appears.

The output is:

Counter({'A': 3, 'B': 3})

Counting is the first step because the answer depends only on how many times each task appears, not on the order of the letters in the input.

Why the most frequent task sets the pace

Think of the schedule as a grid. Each row is one "round", which is a block of n + 1 slots. In a round, each task can run at most once, because after it runs it must wait n slots. The most frequent task is the bottleneck.

Take task A with 4 copies and cooldown n = 2. Each copy must sit at least 3 slots after the previous copy. Its first copy is at slot 1, the second at slot 4 or later, the third at slot 7 or later, and the fourth at slot 10 or later. So the four copies of A alone need at least (4 - 1) * 3 + 1 = 10 slots. The first (4 - 1) gaps each take n + 1 = 3 slots, and the final copy takes one more slot.

Now suppose two tasks share the top count. Say A and B both appear 3 times, with n = 2. The copies of A alone need 7 slots, at 1, 4, and 7. The copies of B fill the gaps at slots 2 and 5, and their last copy needs slot 8. The last row holds one copy of each task that has the top count. The first 6 slots hold the earlier copies, and the 2 tasks in the last row add 2 more slots: (3 - 1) * 3 + 2 = 8.

That gives the formula:

slots needed = (maxCount - 1) * (n + 1) + numberOfTasksWithMaxCount

Here maxCount is the highest count of any single task. numberOfTasksWithMaxCount is how many tasks share that highest count.

There is one more rule. The formula gives a minimum from the bottleneck. It cannot be smaller than the number of tasks, because each task takes one slot. So the final answer is the larger of two numbers:

answer = max(number of tasks, (maxCount - 1) * (n + 1) + numberOfTasksWithMaxCount)

When many different tasks are present, the number of tasks can be bigger than the formula. For example, the tasks ABCDEF with n = 3 have maxCount = 1 and six tasks with that count. The formula gives (1 - 1) * 4 + 6 = 6. The list has 6 tasks, so the answer is 6.

Here is the formula in Python:

The output is:

8
6

The default=0 argument to max handles an empty input. Without it, max raises an error on an empty sequence. The sum(1 for c in ...) line adds 1 for each task whose count equals the top count. It is a generator expression, which produces the values one at a time.

The formula gives the number of slots without building a schedule. It is fast, and it is the answer many interview problems expect. But a formula only says how long the schedule is. It does not show which task runs in which slot. For that you need a simulation, and a heap makes the simulation simple.

Building the schedule with a heap

A max heap is a heap that returns the largest value first. Python's heapq module only builds a min-heap, which returns the smallest value first. To get a max heap, store the negative of each value. The largest count then becomes the most negative number, which is the smallest, so it comes out first. Here the value is the number of copies a task still needs to run.

At every slot, the worker should run the task with the most copies left. This is a greedy choice, which means taking the best option at each step without going back. Running the largest count first works because the tasks with many copies need the most gaps, so they should use the early slots.

When two tasks have the same count, the heap compares the second item of each pair. The code stores the task letter there, so the smaller letter goes first. This makes the output the same on every run.

The heap holds tasks that are ready to run. A second structure, the cooldown queue, holds tasks that just ran and must wait. A queue is a first-in, first-out list: the first item added is the first item removed. Python's collections.deque is a fast queue. Each entry in the cooldown queue records the slot number at which the task becomes ready again.

The loop works like this:

1. Move the time forward by one slot.
2. If the task at the front of the cooldown queue is ready at this slot, move it back into the heap.
3. If the heap is empty, the slot is idle. Write a dash and go to the next slot.
4. Otherwise, take the task with the most copies from the heap and run it. Write its letter.
5. If it still has copies left, add it to the cooldown queue with the slot number time + n + 1 as its ready time.
6. Stop when both the heap and the cooldown queue are empty.

The queue stays in order of ready time, because each new entry is added at a later slot than the one before it. So checking only the front of the queue is enough.

The value time + n + 1 is the detail to get right. A task that runs at slot t may run again at slot t + n + 1. With n = 2, a task at slot 4 can next run at slot 7. Slots 5 and 6 are the two cooldown slots.

The Python code

This module has a function that builds the schedule as a string, one character per slot. The length of the string is the answer. The module also has the formula, and a loop that prints both for several inputs.

The output is:

AAABBB n=2 schedule=AB-AB-AB length=8 formula=8 same=True
AAABBB n=0 schedule=ABABAB length=6 formula=6 same=True
AAAABBBCD n=2 schedule=ABCABDAB-A length=10 formula=10 same=True
AAAAAABCDEFG n=2 schedule=ABCADEAFGA--A--A length=16 formula=16 same=True
ABCDEF n=3 schedule=ABCDEF length=6 formula=6 same=True

The schedule string and the formula agree in every row. Each schedule string is one valid answer. A different tie-breaking rule can print a different string with the same length. The length is the part that is fixed.

The tuple (-remaining, name) and the cooldown entry (time + n + 1, name, remaining - 1) are plain Python tuples. The code unpacks them into names with lines like _, name, remaining = .... The name _ marks a value that is not used.

Worked example 1: AAABBB with n = 2

Trace the loop by hand for AAABBB and n = 2. The counts are A = 3 and B = 3. The heap starts with both tasks. The cooldown queue starts empty. The table lists what happens at each slot. The "ready at" value is the slot number when a task can return to the heap. The heap column lists the tasks in priority order, most copies first.

Each row starts by moving any task that is ready into the heap. Then the worker runs the heap's top task, or sits idle if the heap is empty.

At slot 3, the heap is empty because both tasks are waiting, so the slot is idle. At slot 4, the first A becomes ready, because 4 >= 4. The result is A B - A B - A B, which is 8 slots. The formula also gives 8.

The loop finds this answer without any extra reasoning about gaps. The gaps come out of the ready times.

Worked example 2: AAAABBBCD with n = 2

The counts are A = 4, B = 3, C = 1, and D = 1. The formula picks A as the bottleneck. It has 4 copies, so it needs (4 - 1) * 3 + 1 = 10 slots. Only A has the top count, so the tie term is 1.

The program prints this schedule:

ABCABDAB-A

Slots are counted from 1 here, as in the table above. Check the gaps for A. It runs at slots 1, 4, 7, and 10. Each gap is 3, which is n + 1. The dash at slot 9 is the one moment when nothing is ready, because the last A is not ready until slot 10. The tasks C and D run once each, so they never wait.

This example shows why the greedy choice works. The worker always picks the task with the most copies left. Here A goes first, then B, then the one-copy tasks fill gaps. The one-copy tasks are useful filler, because a task with one copy never needs a second slot after its first run.

Worked example 3: six copies of one task

The third example is harder because the bottleneck task is far more frequent than the rest. Take A six times, plus B, C, D, E, F, and G once each, with n = 2.

The formula gives (6 - 1) * 3 + 1 = 16. The list has 12 tasks, so 12 is not the answer. The formula wins, and the answer is 16.

The program prints:

ABCADEAFGA--A--A

Count the positions. The string has 16 slots, and 12 of them hold a task. The other 4 are idle, at slots 11, 12, 14, and 15. They come from the waiting between the late copies of A. Use this check when you test your own code: the number of dashes plus the number of tasks must equal the answer.

This example teaches a second point. The one-copy tasks fill the early gaps. The idle slots that remain come from the copies of A, which must wait for their cooldown after slot 10. The formula counts those idle slots through the (maxCount - 1) * (n + 1) term.

Common mistakes

Off by one in the ready time

The most common bug is writing time + n instead of time + n + 1. This is an off-by-one error, a mistake of one step in a count. The difference looks small, but the schedule becomes invalid. Here is the same program with that one change. Only the ready time changed.

The output is:

ABABAB
ABABABACD

The first line shows the problem. The schedule ABABAB puts the two A copies at slots 1 and 3. Their gap is 2, but the cooldown is 2, so the copies need a gap of 3. The output is shorter than the correct answer of 8, so the program is wrong even though it prints a result.

A useful habit is to write a small checker that reads the schedule and confirms the gap between any two copies of the same letter is at least n + 1. It also confirms that every task appears the right number of times. Run the checker on every output, not only on the examples you already know.

The output is:

True
False
False

The checker returns False for the wrong schedule. The last line also returns False, because its counts do not match the input: the string has three A and four B, but the input has four A and three B.

Using only the highest count

Some people write the formula with only maxCount:

return max(len(tasks), (max_count - 1) * (n + 1) + 1)

This drops the tie term. For AAABBB with n = 2, the result is (3 - 1) * 3 + 1 = 7. The correct answer is 8, because A and B both have the top count, and both need a slot in the last row. The schedule AB-AB-AB has 8 slots, and no valid schedule has 7. Counting the tasks that share the top count fixes the formula.

Forgetting the idle slot

If the code does not append a dash when the heap is empty, the schedule string is shorter than the true time. The time counter keeps going, but the string does not. Always count the idle slots, because the worker still spends that time waiting. The dash keeps the string in step with time, which moves forward on every pass.

Missing import

Python needs an import line for each module that is not built in. If the import heapq line is missing, the first call to heapq fails. Here is the error from a short program that uses heapq without importing it:

NameError: name 'heapq' is not defined. Did you mean: 'heap'? Or did you forget to import 'heapq'?

The message names the missing module, heapq. The fix is the line import heapq at the top of the file. The same kind of error appears for deque if from collections import deque is missing. The "Did you mean" hint depends on the other names in your code, so your message can differ.

Practice

Exercise 1

Find the minimum time for the tasks AAAAB with n = 1. Use the formula, then check your answer by writing one valid schedule.

Show the answer

The count of A is 4, which is the highest. Only A has that count, so the tie term is 1. The formula gives (4 - 1) * (1 + 1) + 1 = 7. The number of tasks is 5, which is less than 7, so the answer is 7. One valid schedule is ABA-A-A, which has 7 slots. The copies of A sit at slots 1, 3, 5, and 7. Each gap is 2, which is n + 1. The program in this lesson prints the same string when it runs on this input.

Exercise 2

Find the minimum time for XXYY with n = 3. Write the schedule.

Show the answer

Both X and Y appear twice. The highest count is 2, and two tasks share it, so the tie term is 2. The formula gives (2 - 1) * (3 + 1) + 2 = 6. The number of tasks is 4, which is less than 6, so the answer is 6. One schedule is XY--XY. The copies of X sit at slots 1 and 5, a gap of 4, which is n + 1. The copies of Y sit at slots 2 and 6, also a gap of 4.

Exercise 3

Explain in plain words why the number of tasks can be bigger than the formula's value, and give an input where that happens.

Show the answer

The formula only counts the waiting caused by the most frequent task. When many different tasks are present, each one still needs its own slot, and the total cannot be less than the number of tasks. The input ABCDEF with n = 0 has a formula value of (1 - 1) * 1 + 6 = 6, which matches the number of tasks here. For a case where the list is longer, take AABCDE with n = 0. The formula term is (2 - 1) * 1 + 1 = 2, but the list has 6 tasks, so the answer is 6.

Exercise 4

A task runs at slot 10. The cooldown n is 2. At what slot can the same task run again? Explain how the code gets that number.

Show the answer

The task can run again at slot 13. The code stores time + n + 1 as the ready time, which is 10 + 2 + 1 = 13. The two cooldown slots are 11 and 12. The + 1 is needed because the task itself took slot 10, and the cooldown counts only the slots after it.

Exercise 5

Trace the code by hand for AAB with n = 1. Write the schedule and its length, then confirm the formula.

Show the answer

The counts are A = 2 and B = 1. The heap starts with A2 and B1. At slot 1, the code runs A, which has the most copies. A now has 1 copy left and is ready at slot 1 + 1 + 1 = 3. At slot 2, the heap holds only B, so B runs. At slot 3, A is ready and runs again. The schedule is ABA, with length 3. The formula gives (2 - 1) * (1 + 1) + 1 = 3, which agrees.

Summary

• Count how many times each task appears. The answer depends on the counts, not on the input order.
• The formula max(number of tasks, (maxCount - 1) * (n + 1) + tasks with maxCount) gives the minimum time directly.
• A max heap, built with heapq from negative counts, always picks the task with the most copies left, and a deque cooldown queue holds tasks until their ready slot.
• A task that runs at slot t is ready again at slot t + n + 1. Using t + n is an off-by-one error that produces an invalid schedule.
• Check every schedule with a small test that confirms the gaps, and check that the schedule length matches the formula.