Job Sequencing with Deadlines

Job Sequencing with Deadlines is a classic greedy scheduling problem. Each job earns a profit but must finish by its own deadline, and you can only run one job per time unit. The trick is realizing that profit-first ordering, combined with placing each job as late as legally possible, is provably optimal.

The slow way first

You could try every subset of jobs, check each ordering for deadline feasibility, and keep the best. That is exponential — 2ⁿ subsets — and hopeless beyond a handful of jobs.

The question to ask: if I want the most profit, which job should I never give up? The most profitable one. So sort by profit, take the richest job first, and only fall back when there is physically no room for it.

The idea: richest first, latest slot

Sort jobs by profit descending. Keep an array of time slots 1 … maxDeadline. For each job, scan backward from its deadline looking for the latest empty slot. If you find one, place the job there and bank its profit. If every slot up to its deadline is full, skip the job.

Why the latest free slot rather than the earliest? Filling late leaves the early slots open for jobs with tight (small) deadlines that have nowhere else to go. That is what makes the greedy choice safe.

Walk through it

Step through the animation. Jobs are sorted A:100, B:50, C:40, D:30. A takes slot 2 (its deadline). B takes slot 1. C wants a slot ≤ 2 but both are full, so it is dropped; D wants slot 1, also full, so it is dropped too. Final profit: 150.

Pseudocode

sort jobs by profit, descending
slot[1 .. maxDeadline] = all empty
profit = 0
for each job (richest first):
    t = job.deadline
    while t >= 1 and slot[t] is filled:
        t = t - 1                 # walk to an earlier slot
    if t >= 1:                    # found a legal empty slot
        slot[t] = job.id
        profit = profit + job.profit
    # else: no room, skip this job
return profit, slot

The Python solution

def job_sequencing(jobs):
    jobs.sort(key=lambda j: j.profit, reverse=True)
    slot = [None] * max(j.deadline for j in jobs)
    profit = 0
    for job in jobs:
        t = job.deadline - 1
        while t >= 0 and slot[t] is not None:
            t -= 1
        if t >= 0:
            slot[t] = job.id
            profit += job.profit
    return profit, slot

• We sort by profit in reverse so the most valuable job is considered first.
• slot is zero-indexed, so deadline d maps to index d - 1; we walk back with t -= 1.
• The while loop finds the latest empty slot at or before the deadline.
• Lines 9-11 are the commit: if a legal empty slot exists we place the job and add its profit.
• If t falls below 0 the job had no room, and we simply move on to the next one.

Complexity

The sort dominates at O(n log n); the slot scan adds O(n·d) in the simple version. A union-find that points each slot to the next free one earlier collapses the scan to near-constant time.

When this pattern shows up

Practice