Job Sequencing Problem

Richest job first, into the latest slot it can still make

time O(n log n + n * d)space O(d)

Two greedy choices are stacked here and both matter. Considering jobs in descending profit order means a job is only ever refused by jobs worth more than it, so no swap could improve the answer. Then placing each accepted job in the LATEST free slot at or before its deadline is what keeps the early slots — the only slots a tight-deadline job can use — free for as long as possible. Take the earliest free slot instead and you block jobs you could have kept.

Details

Animated on: jobs (deadline, profit) = A(2,100), B(1,19), C(2,27), D(1,25), E(3,15) — each job takes one unit of time and earns its profit only if it finishes by its deadline. Maximize total profit.

Problem:Job Sequencing ProblemMedium

Richest job first, into the latest slot it can still make

step 1 / 9

t1 -

[0]

t2 -

[1]

t3 -

[2]

Sort by profit, richest first: A(d2,p100), C(d2,p27), D(d1,p25), B(d1,p19), E(d3,p15). Every job takes exactly one time unit, so the board is 3 empty slots — the largest deadline in the input. Offering each job the money-first order means a job is only ever refused by jobs that pay more than it.

Pseudocode

1FUNCTION jobSequencing(jobs)
2  SORT jobs BY profit DESCENDING
3  maxDeadline <- MAX(deadline OF jobs)
4  slot[1..maxDeadline] <- EMPTY
5  total <- 0
6  FOR EACH job IN jobs
7    FOR t <- MIN(job.deadline, maxDeadline) DOWN TO 1
8      IF slot[t] = EMPTY THEN
9        slot[t] <- job
10        total <- total + job.profit
11        BREAK
12  RETURN total

← / → step · space play · Home restart

Every step in words

Show all 9 steps

Sort by profit, richest first: A(d2,p100), C(d2,p27), D(d1,p25), B(d1,p19), E(d3,p15). Every job takes exactly one time unit, so the board is 3 empty slots — the largest deadline in the input. Offering each job the money-first order means a job is only ever refused by jobs that pay more than it.
A(d2,p100) lands in slot t2 — the latest slot its deadline allows, and it is free. Taking the LAST legal slot keeps the earlier ones open for jobs whose deadlines are tighter. Profit = 100.
C(d2,p27) wants slot t2, but A already holds it and pays 100 — more than this job's 27. Never evict a richer job; step back one slot instead.
C(d2,p27) lands in slot t1 — t2 was taken, so it fell back to the latest slot still free. Taking the LAST legal slot keeps the earlier ones open for jobs whose deadlines are tighter. Profit = 127.
D(d1,p25) wants slot t1, but C already holds it and pays 27 — more than this job's 25. Never evict a richer job; step back one slot instead.
D(d1,p25) must run by t1, and slots t1..t1 are all filled with jobs paying at least 25. There is nowhere left to put it, so it is dropped. Profit stays 127.
B(d1,p19) must run by t1, and slots t1..t1 are all filled with jobs paying at least 19. There is nowhere left to put it, so it is dropped. Profit stays 127.
E(d3,p15) lands in slot t3 — the latest slot its deadline allows, and it is free. Taking the LAST legal slot keeps the earlier ones open for jobs whose deadlines are tighter. Profit = 142.
Board is settled: t1=C, t2=A, t3=E. 3 of 5 jobs run, for a maximum profit of 142.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Job Sequencing Problem in the editor All Greedy problems Back to roadmap