AlgoScope

Job Sequencing with Deadlines

Richest job first, placed in the latest free slot before its deadline. No free slot means it is dropped.

Greedy, algorithm, intermediate
Job a in slot 2.123jobprofita100
Job a in slot 2.123jobprofita100

Intervals and Greedy Choices: Job sequencing with deadlines

Decision, step 2 of 7

Job a, profit 100, deadline 2: slot 2 is free, so it goes there. Total profit 100.

How intervals and greedy choices works

Cost

Best
O(n log n)
Average
O(n^2)
Worst
O(n^2)
Space
O(n)

O(n log n) with union-find over slots.

Taught by the same lesson

Intervals and Greedy Choices covers these too, in the same run.