Job Sequencing Problem
Job Sequencing Problem: each job takes 1 unit of time, has a deadline and a profit. Maximize profit by scheduling at most one job per slot, each before its deadline.
- 1 <= n <= 10⁵
- 1 <= deadline[i] <= n
- 1 <= profit[i] <= 10⁵
- Each job takes exactly one unit of time
Intuition
The job sequencing problem gives jobs that each take one unit of time, carry a deadline and a profit, and asks for the maximum profit when only one job runs per time slot and each must finish by its deadline. Two greedy instincts compete here, and only one is right. Scheduling by earliest deadline maximises the number of jobs, not the profit — a low-value urgent job would displace a valuable one. Since the objective is profit, commit to the most profitable jobs first. But sorting by profit is only half the rule. The second half is where to place each job, and it matters just as much: - Place each job in the latest free slot at or before its deadline. Placing late is what keeps the schedule flexible. If a job with deadline 5 is placed at slot 5, then slots 1 through 4 stay open for jobs with tighter deadlines. Placing it at slot 1 instead would consume the only slot a deadline-1 job could ever use, losing that job for no gain — the profitable job is scheduled either way. So the algorithm is: sort by profit descending, and for each job scan backwards from its deadline for the first free slot. If none exists, the job cannot be scheduled at all and is skipped. The backward scan makes this O(n · maxDeadline). A union-find structure that maps each slot to the next free slot below it reduces the lookup to near-constant, giving O(n log n) overall.
Greedy with a twist: sort by profit descending, then place each job as late as its deadline allows. Scheduling late keeps the early slots free for jobs that might have tighter deadlines. Whenever a greedy choice must also preserve room for future choices, ask which placement is least disruptive — that's usually the latest legal one.
Approach
Before reading on: price up what sorting first costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n log n + n·D) time and O(D) space.
Sort by profit, not by deadline
The objective is total profit, so the richest jobs get first refusal on the schedule. Sorting by deadline instead maximises the job count, which is a different problem with a different answer.
Size the slot array by the largest deadline
No job can be scheduled beyond the maximum deadline, so an array of that many boolean slots is enough. Slots are typically 1-indexed to match deadline values directly and avoid off-by-one errors.
Place each job as late as its deadline allows
Scan from the job's deadline downward for the first free slot. Late placement preserves earlier slots for jobs with tighter deadlines — this is the part people miss, and taking the earliest free slot instead silently loses profit.
Skip a job with no free slot
If every slot from the deadline down to 1 is taken, this job cannot run at all. Skip it and continue — later jobs have lower profit but may have later deadlines and still fit.
Speed the slot search with union-find
A disjoint-set structure where each slot points to the next free slot at or below it turns the backward scan into a near-constant find. This drops the total from O(n · maxDeadline) to O(n log n), which matters when deadlines are large.
Cost of the two versions
Sorting is O(n log n). The simple backward scan adds O(n · maxDeadline) in the worst case, while the union-find version keeps the total at O(n log n). Space is O(maxDeadline) for the slot array either way.
Solution & live demo
Common pitfalls
Sorting by deadline instead of profit
jobs.sort(key=lambda j: j[1])
jobs.sort(key=lambda j: -j[2])
Slots are the scarce resource, so the greedy must spend them on the most valuable jobs first. Ordering by deadline fills early slots with whatever happens to be urgent, and a high-profit job arriving later finds nothing free.
Placing each job at the earliest free slot
for t in range(1, min(d, max_d) + 1):
if slot[t] is None: ...for t in range(min(d, max_d), 0, -1):
if slot[t] is None: ...Taking an early slot for a job with a distant deadline steals the only slot a tight-deadline job could ever use. Scanning backwards from the deadline leaves the maximum room for everything still to come.
Sizing the slot array by job count
slot = [None] * (len(jobs) + 1)
max_d = max(j[1] for j in jobs) slot = [None] * (max_d + 1)
Deadlines are time units, not job indices, and a deadline may exceed the number of jobs. The array must span the largest deadline, and the + 1 keeps it 1-indexed so slot numbers read as times.
Edge cases
Only one slot exists — the single most profitable job is chosen.
Jobs failing to find a free slot are skipped, by construction the cheapest ones.