Job Sequencing with Deadlines
Richest job first, placed in the latest free slot before its deadline. No free slot means it is dropped.
Intervals and Greedy Choices: Job sequencing with deadlines
Job a, profit 100, deadline 2: slot 2 is free, so it goes there. Total profit 100.
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.
Before this
Related
Taught by the same lesson
Intervals and Greedy Choices covers these too, in the same run.