How to build a job scheduler in code

In this article

1. Before you start
2. Why interviewers ask this
3. Schedulers in code from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the machine coding rounds guide, where scheduler problems appear next to other applied coding tasks.

Why interviewers ask this

A scheduler is a small system that forces several decisions in one problem: which data structure orders the work, how dependencies are tracked, and what happens when jobs are cancelled or fail. Candidates have reported prompts of this family in applied coding rounds, for example a task system with priorities and dependencies, a job scheduler with creation, persistence, dispatching and execution, and a build system that grows from task ordering to graph execution, caching and parallelism.

A weak answer sorts a list every time a job arrives and ignores dependencies. A strong answer picks a heap, explains the tie-break, runs only ready jobs and says what the design does when a job is cancelled. A Staff-level answer also names the failure modes: starvation, cycles, and a job that runs twice after a crash. The low level design question list covers related design problems.

Schedulers in code from first principles

Job scheduler

A job scheduler is a component that holds jobs, each with a priority, a duration and optional dependencies, and decides which job a free worker runs next, so that important work goes first and no job starts before the jobs it needs have finished.

Ready queue

A ready queue is the collection of jobs that are allowed to start now because all their dependencies are done; the scheduler picks the next job only from this collection, in order of priority.

Makespan

The makespan is the time from the start of a batch of jobs to the end of its last job, so it measures how long the whole batch takes rather than how long any single job takes.

In plain words

Think of a kitchen with a stack of order tickets. Some dishes cannot start until another is done, because the sauce goes on the pasta. A head cook looks only at tickets that can start now. The cook takes the most urgent one and hands it to a free cook. When a dish finishes, tickets waiting on it become ready. The analogy breaks in one place. A real cook can see the whole room. A scheduler in code sees only the data structures you give it.

In one precise sentence, a scheduler keeps a priority queue of ready jobs, tracks which jobs still wait on others, and repeats "pick the best ready job, give it to a free worker, mark it done, release its children" until nothing is left.

Step 1: A min-heap holds the ready jobs

A min-heap is a tree stored in a list in which every parent is no larger than its children, so the smallest item always sits at the front. The Python documentation states that the smallest element of a min-heap is always the root, undefined. Pushing and popping keep that property without sorting the whole list.

The heap is not a sorted list. Pushing the priorities 5, 3, 8, 1 and 4 (illustrative) produces the list [1, 3, 8, 5, 4], while the sorted order is [1, 3, 4, 5, 8].¹ Only the front is certain to be the smallest, which is exactly what a scheduler needs: the best job now.

A heap of n items is a complete binary tree, so its height is floor(log2 n); for 1,000,000 items (illustrative) that is 19.¹ Push and pop move an item along one path of that height, so each costs O(log n). Reading the best job, heap[0], costs O(1). Re-sorting on every arrival costs O(n log n) each time. You now know the container; the next step makes its order stable.

Step 2: A counter in each entry keeps equal priorities in arrival order

A tie-breaker is an extra field in each heap entry that decides the order of entries whose priorities are equal. Without one, Python compares the next field in the tuple, which may be a job name or an object that cannot be compared at all. The heapq notes recommend storing the priority, an entry count and the task; the count returns equal-priority tasks in the order they were added, and because no two counts match, the comparison never reaches the task itself.

Three jobs named z, y and x, all with the same priority and pushed in that order (illustrative), pop as x, y, z when the name is the tie-breaker, which is alphabetical order, and as z, y, x with a counter, which is first in, first out (FIFO) order.¹ The entry is (priority, next(counter), job). Input: a job and its priority. Output: an entry that always compares cleanly and keeps arrival order.

Step 3: Only jobs whose dependencies are done enter the queue

A topological order is a linear ordering of the jobs in which every job comes after the jobs it depends on. The graphlib documentation says such an order exists if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

A scheduler does not need the full order in advance. It needs the jobs that are ready now, so it keeps a count of unfinished dependencies per job and a list of children per job. When a job finishes, each child's count drops by one, and a child that reaches zero enters the ready queue.

Python's TopologicalSorter does this for you: prepare() checks for cycles and raises CycleError, get_ready() returns the jobs that can start, and done() marks a job finished. Each job and each dependency is handled once, which costs O(V + E) for V jobs and E dependencies. Every job is also pushed onto and popped from the heap once, at O(log V) each, so the whole loop costs O((V + E) + V log V).

Step 4: Free workers take the best ready job

Workers are the things that run jobs, such as threads or processes. The scheduler loop fills every idle worker with the best ready job, then waits for the next job to finish. When one finishes, the worker becomes free, the job is marked done, its children may become ready, and the loop repeats. The code below simulates this with a clock that jumps to the next finish time, which is the usual way to test a scheduler without sleeping.

import heapq, itertools
from graphlib import TopologicalSorter

def run(jobs, workers):
    """jobs: name -> (priority, duration, deps). Lower priority number runs first."""
    sorter = TopologicalSorter({n: set(deps) for n, (_, _, deps) in jobs.items()})
    sorter.prepare()                      # raises CycleError on a cycle
    count = itertools.count()             # tie-breaker: arrival order
    ready, running, log = [], [], []      # two heaps and the dispatch log
    clock, free = 0, workers

    def enqueue():
        for name in sorter.get_ready():   # only jobs whose dependencies are done
            heapq.heappush(ready, (jobs[name][0], next(count), name))

    enqueue()
    while ready or running:
        while ready and free:             # fill idle workers, best job first
            _, _, name = heapq.heappop(ready)
            free -= 1
            heapq.heappush(running, (clock + jobs[name][1], name))
            log.append((name, clock, clock + jobs[name][1]))
        clock, name = heapq.heappop(running)   # jump to the next finish time
        sorter.done(name)
        free += 1
        while running and running[0][0] == clock:
            sorter.done(heapq.heappop(running)[1])
            free += 1
        enqueue()
    return log, clock

The second heap, running, is keyed on finish time, so the same structure that orders jobs by priority also orders events by time. You now have the whole scheduler: a heap, a counter, dependency tracking and a worker loop.

1 · Min-heap2 · Counter3 · Dependencies4 · WorkersReplay

Step-by-step description

1. Ready jobs sit in a min-heap.
2. A counter keeps ties in arrival order.
3. Only jobs with no unfinished parents enter.
4. Free workers take the best job.

• The ready queue is a min-heap that returns the best job first.
• A counter breaks ties so equal priorities keep arrival order.
• A job enters the queue only when its dependencies are done.
• Free workers take the best ready job.

Worked example

Five illustrative jobs show the loop. Each has a priority (lower runs first), a duration in time units and dependencies: job A has priority 2, duration 3 and no dependencies; B has 1, 2 and none; C has 1, 4 and needs A; D has 3, 2 and needs A; E has 1, 1 and needs B and C.¹

On one worker the dispatch order is B, A, C, E, D and the makespan is 12 time units, which equals the total work of 12 because the worker never idles.¹ A starts second because B is the only other job ready at the start and it has the better priority. D runs last: it is ready at time 5, but C and then E both have a better priority.

On two workers, B and A start at time 0. When A finishes at time 3 it releases C and D, which start together. C ends at 7, then E runs from 7 to 8, so the makespan is 8.¹ The longest chain of dependent jobs, A then C then E, takes 3 plus 4 plus 1, which is 8, so no number of workers can finish this batch sooner.¹

Text description of the diagram

• With two workers the five jobs finish at time 8 instead of 12.
• Jobs C and D start together at time 3 when job A finishes.

Trade-offs and edge cases

The ordering rule changes the result. Take four illustrative jobs of lengths 6, 8, 7 and 3, all waiting at time 0. Running them in arrival order gives an average wait of 10.25 time units; running the shortest first gives 7.¹ Shortest-job-first needs the durations in advance, and a steady stream of short jobs can delay a long one forever. That delay is called starvation. A common fix is to raise a job's priority the longer it waits, which is called aging.

Text description of the diagram

• First come first served averages 10.25 time units of waiting.
• Shortest job first averages 7 time units of waiting.

Edge cases a scheduler design should cover:

• Cancelling or changing a priority. Removing an arbitrary entry with list.remove breaks the heap order, and an index-tracked delete is possible but fiddly. The heapq notes suggest marking the entry as removed, adding a new entry with the revised priority, and skipping removed entries when popping.
• Cycles. If A needs B and B needs A, neither ever becomes ready. prepare() raises CycleError for this, so the scheduler can reject the batch early.
• Delayed jobs. A job that must run at a given time is the same queue keyed on the run time. Prefer a monotonic clock for delays, since it cannot go backwards and system clock updates do not affect it, while the wall clock can jump.
• Persistence and crashes. A durable scheduler stores each job's state in a database. If a worker dies mid-job, the job may run twice after recovery, so jobs should be safe to repeat.
• Different problem, same words. Finding the minimum time to finish M tasks on N central processing units (CPUs) is a load-balancing question, not a priority-queue one, and it has two versions. If the tasks must stay in order and each CPU takes a contiguous block, binary-search the finish time and check each guess greedily in O(M) steps. If any task may go on any CPU, no known method is fast and exact on every input. The interview answer is backtracking against a bound, or the heuristic of giving the longest task to the least-loaded CPU first, using a heap keyed on load like the running heap above. A heuristic can miss the true minimum.
• Related variants. To find the top k longest-running jobs, keep a min-heap of size k and drop the smallest when it grows past k, which costs O(n log k) for n jobs. For maximum profit with deadlines when every job takes one time unit, sort by deadline, push each reward onto a min-heap, and pop the smallest whenever the heap holds more jobs than the deadline allows. A build system adds caching by skipping a job whose inputs have not changed since its last run.

For a worked in-memory design that grows level by level, see the CodeSignal in-memory database walkthrough, and for ordering events by time see event and log processing problems.

How to answer it in an interview

The spoken structure: name the heap, name the tie-break, explain how dependencies gate the queue, then give the failure modes.

Common mistakes

• "I sort the list of jobs each time one arrives." (wrong) That costs O(n log n) per arrival instead of O(log n). (right) "A heap gives me the best job at the front, and I push and pop as jobs arrive and finish."
• "A heap is a sorted list." (wrong) Only the front is certain to be the smallest. (right) "Only the root is the smallest; the rest of the list is partly ordered."
• "Equal priorities will run in the order they came in." (wrong) Nothing in a heap promises that. (right) "I store a counter in each entry so ties break by arrival."
• "I push every job into the queue and check dependencies when I pop." (wrong) That can pop a job that cannot start and forces a re-push. (right) "Only ready jobs enter the queue; finishing a job releases its children."
• "Shortest job first is always best." (wrong) It needs known durations and can starve long jobs. (right) "It lowers the average wait when durations are known; I add aging to protect long jobs."

Follow-up questions

How do you design a task management system with priority handling and dependency resolution?

Use the four steps above: a min-heap with a counter for ready jobs, dependency counts that release children when a job finishes, and a worker loop. Add cycle detection at submission, and say how cancellation and starvation are handled.

How do you write the low level design code for a job scheduler covering creation, persistence, dispatching and execution?

Model a Job with an identifier, priority, duration, dependencies and a state such as pending, ready, running, done or failed. Keep a store that saves state changes, a dispatcher that owns the ready heap, and an executor that runs jobs and reports back. The low level design question list covers the class-design habits behind this.

How do you cancel or reprioritise a job that is already in the queue?

Mark its entry as removed and, for a new priority, push a fresh entry; the pop loop skips removed entries. This avoids breaking the heap and is the approach in the Python documentation.

How do you find the minimum time to finish M tasks on N CPUs?

Minimum finish time on N CPUs is a load-balancing problem, not a priority-scheduler problem. If tasks must stay in order, binary-search the finish time with a greedy O(M) check. If any task can go on any CPU, use backtracking against a bound, or the longest-task-first heuristic on a heap keyed on load, and say it is a heuristic. Say that you are changing problems before you start.

What changes if jobs must survive a restart?

Write each state change to durable storage before acting on it, reload pending and running jobs on start, and treat running jobs as unfinished. Because a job may then run twice, make jobs safe to repeat. Delayed jobs are reloaded the same way, keyed on their run time, as in caches with a time to live (TTL), covered in TTL caches and time-based key-value stores.

Sources

1. heapq: Heap queue algorithm, Priority Queue Implementation Notes (Python 3 documentation) — Python Software Foundation, 26 Oct 2026
2. graphlib: TopologicalSorter (Python 3 documentation) — Python Software Foundation, 26 Oct 2026
3. time.monotonic (Python 3 documentation) — Python Software Foundation, 26 Oct 2026