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.
Open on GeeksforGeeks ↗Intuition
Take jobs in profit order — but place each as late as its deadline allows. Placing late keeps earlier slots free for jobs with tighter deadlines, so a rich job never squeezes out another it didn't have to.
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
Sort by profit, descending
If a job can be scheduled at all, we'd rather it be a high-profit one — commit to the richest first.
Place each in its latest free slot
For a job with deadline d, scan slots d, d−1, … 1 for a free one. Late placement preserves options for tighter jobs.
Optional speed-up
The slot scan can use a union-find 'next free slot' structure to reach O(n log n); the simple scan is O(n·maxD).
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.