Job Scheduling with Deadlines

Schedule jobs to maximize total profit by placing each job into the latest available slot before its deadline. Greedy is optimal by exchange arguments.

Algorithm Steps

Sort jobs by decreasing profit.
For each job, try to place it at its latest free slot ≤ deadline.
Skip if no slot free.

Speed (ms)

Slot 1

Slot 2

Slot 3

Pseudocode

1procedure JOB_SCHEDULING(jobs)
2  sort jobs by decreasing profit
3  let slots[1..maxDeadline] ← empty
4  for each job j in jobs do
5    for t ← min(maxDeadline, j.deadline) down to 1 do
6      if slots[t] is empty then
7        slots[t] ← j; break
8      end if
9    end for
10  end for
11  return slots
12end procedure

Practice Problems

Job Sequencing (GFG)
CP-Algorithms: Job Scheduling

Use Cases

Manufacturing job sequencing on a single machine.
Content publishing with deadlines and priorities.
Ad campaign scheduling with time windows.

Back to Huffman Coding Next: Coin Change Greedy