GreedyGreedy
Job Sequencing with Deadlines
Schedule unit-length jobs with deadlines and profits to maximize total profit: take jobs in profit order and place each in the latest free slot before its deadline.
A
A
A
B
C
C
D
D
E
F
F
F
F
Time slots (one unit each)
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| · | · | · | · |
Jobs, most profitable first
| id | deadline | profit | slot |
|---|---|---|---|
| A | 3 | 100 | — |
| B | 1 | 90 | — |
| C | 2 | 60 | — |
| D | 2 | 50 | — |
| E | 1 | 40 | — |
| F | 4 | 30 | — |
1/196 jobs, each taking exactly one unit of time and each worth its profit only if it finishes by its deadline. Row A's filled cells are the slots it is still allowed to run in — its feasible window [1, 3] — so this is the same interval picture as before, with "time unit" meaning "slot". We choose a subset and an assignment maximising total profit.
Slot being probedSlot this job was scheduled inFeasible window of a scheduled jobRejected job — no free slot before its deadline
PseudocodeLearn Job Sequencing with Deadlines →
1sort jobs by profit, highest first2slot[1 .. maxDeadline] = free3for each job (deadline, profit):4 t = deadline5 while t >= 1 and slot[t] is taken: t -= 1 # latest free slot6 if t >= 1:7 slot[t] = job; total += profit8 else:9 reject the job # every slot up to its deadline is full10return slot, totalVariables
jobs6
slots4
profit0
Complexity
worst O(n log n + n · α(n))
space O(n + maxD)
Speed