Job Sequencing Problem with Deadlines β Greedy Algorithm
- Sort by profit descending β greedily assign highest-profit jobs first.
- Assign each job to the latest available slot β€ its deadline.
- Naive O(nΒ²); Union-Find optimisation achieves O(n log n).
Job scheduling with deadlines is a classic operations research problem that appears in OS scheduling, manufacturing planning, and project management. The greedy insight β schedule highest-paying jobs as late as possible within their deadlines β is counterintuitive: you might expect to schedule early, but scheduling late preserves earlier slots for potentially higher-value jobs that might arrive.
The Union-Find optimisation that reduces O(n^2) to O(n log n) is an elegant application of the disjoint set data structure in a non-graph context β a useful demonstration that Union-Find is about more than just connected components.
Greedy Algorithm
Sort jobs by profit descending. For each job, find the latest available slot before its deadline and assign it there.
def job_scheduling(jobs: list[tuple]) -> tuple[int, list]: """ jobs: list of (job_id, deadline, profit) Returns (total_profit, scheduled_job_ids) """ jobs = sorted(jobs, key=lambda x: x[2], reverse=True) max_deadline = max(d for _, d, _ in jobs) slots = [None] * (max_deadline + 1) # slots[1..max_deadline] total = 0 scheduled = [] for job_id, deadline, profit in jobs: # Find latest free slot at or before deadline for slot in range(deadline, 0, -1): if slots[slot] is None: slots[slot] = job_id total += profit scheduled.append(job_id) break return total, scheduled jobs = [('a',2,100), ('b',1,19), ('c',2,27), ('d',1,25), ('e',3,15)] print(job_scheduling(jobs)) # (142, ['a', 'c', 'e'])
Union-Find Optimisation β O(n log n)
The naive slot-finding is O(n) per job β O(nΒ²) total. Using Union-Find (disjoint set), we can find the latest free slot in near-O(1) amortised time, giving O(n log n) overall.
def find(parent, i): if parent[i] != i: parent[i] = find(parent, parent[i]) return parent[i] def job_scheduling_uf(jobs): jobs = sorted(jobs, key=lambda x: x[2], reverse=True) max_d = max(d for _, d, _ in jobs) parent = list(range(max_d + 2)) total, scheduled = 0, [] for job_id, deadline, profit in jobs: slot = find(parent, deadline) if slot > 0: parent[slot] = slot - 1 # mark slot as used total += profit scheduled.append(job_id) return total, scheduled
Complexity
Naive: O(n log n) sort + O(nΒ²) slot finding = O(nΒ²) Union-Find: O(n log n) sort + O(n Ξ±(n)) slot finding β O(n log n)
For most interview purposes the naive O(nΒ²) implementation is sufficient.
π― Key Takeaways
- Sort by profit descending β greedily assign highest-profit jobs first.
- Assign each job to the latest available slot β€ its deadline.
- Naive O(nΒ²); Union-Find optimisation achieves O(n log n).
- Classic greedy problem β the exchange argument shows this is optimal.
- Appears frequently in scheduling interview problems.
Interview Questions on This Topic
- QWhy do we assign jobs to the latest possible slot rather than earliest?
- QWhat data structure optimises slot-finding to O(log n)?
- QProve that sorting by profit and taking the latest available slot is optimal.
Frequently Asked Questions
What if no slot is available for a job?
Skip it β this is the greedy choice. Taking a lower-profit job that fits would only reduce total profit.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.