Pattern visualizer
Job Sequencing Problem
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. 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..
Richest job first, into the latest slot it can still make
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.
1FUNCTION jobSequencing(jobs)2 SORT jobs BY profit DESCENDING3 maxDeadline <- MAX(deadline OF jobs)4 slot[1..maxDeadline] <- EMPTY5 total <- 06 FOR EACH job IN jobs7 FOR t <- MIN(job.deadline, maxDeadline) DOWN TO 18 IF slot[t] = EMPTY THEN9 slot[t] <- job10 total <- total + job.profit11 BREAK12 RETURN total
← / → step · space play · Home restart