Job Scheduling
Each job earns a profit if completed by its deadline, one job per time slot. Sorting by profit and greedily placing each job in the latest still-free slot at or before its deadline maximises total profit.
- Category
- Greedy
- Time complexity
- O(n²) simple, O(n log n) w/ DSU
- Space complexity
- O(deadline)
Pseudocode
sort jobs by profit, descending for each job: find the latest free slot ≤ deadline if found: place it, add profit if none: skip the job
Reference implementation
jobs.sort(key=lambda j: -j.profit)
for j in jobs:
for t in range(min(j.deadline, maxSlot), 0, -1):
if slot[t] is None: slot[t] = j; break