1. One-Liner
Job sequencing sorts jobs by profit, then places each job in the latest free slot before its deadline—maximizing total profit when each job takes unit time.
2. The Problem It Solves
Each job has (profit, deadline), one unit duration, one machine. Schedule a subset without missing deadlines to maximize sum of profits.
3. The Core Idea
Take rich jobs first; for each, squeeze it into the last empty minute ≤ deadline. This leaves earlier slots for more jobs—classic greedy with union-find or boolean slot array.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Sort | Jobs by descending profit |
| 2. Slots | Track free time slots 1..maxDeadline |
| 3. Place | For each job, find latest free slot ≤ deadline |
| 4. Sum | Add profits of scheduled jobs |
5. Dry Run Example
Jobs (p,d): (100,2), (19,1), (27,2), (25,1), (15,3). Sorted by profit: take (100,2) slot 2, (27,2) slot 1, (25,1) no slot, … finalize max profit selection.
6. Key Properties
| Property | Value |
|---|---|
| Unit jobs | Standard greedy works |
| Non-unit | Problem changes (NP-hard variants) |
7. Where It Is Used
| Domain | Use |
|---|---|
| Ops research | Single-machine profit scheduling |
| Interviews | Greedy + DS pattern |
8. Interview Tips
Mention O(n²) slot scan or O(n log n) with DS; clarify one slot per time unit.
9. Comparison with Other Approaches
| Approach | Notes |
|---|---|
| Greedy by profit | Optimal for unit-time max profit |
| EDD rule | Different objective (lateness) |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n²) naive slots; O(n log n) with efficient DS |
| Space | O(d) for slots |
Implementation Example (PYTHON)
def job_sequencing(jobs):
# jobs: list of (profit, deadline)
jobs.sort(key=lambda x: -x[0])
max_d = max(d for _, d in jobs) if jobs else 0
slot = [False] * max_d
profit = 0
for p, d in jobs:
for t in range(min(d, max_d) - 1, -1, -1):
if not slot[t]:
slot[t] = True
profit += p
break
return profit