Given a set of jobs, each worth a profit and each due by a deadline, and a machine that can run
exactly one job per unit of time starting at t=1 — every job takes exactly one time
unit — pick which jobs to run, and when, to earn the most total profit. A job earns its profit only
if it finishes at or before its own deadline; miss it and that job earns nothing, so there's no
partial credit for starting late. This is a scheduling problem with a hard constraint (deadlines)
and a soft objective (maximize profit), and unlike Activity
Selection's problem shape — where every accepted item's time slot is fixed by the data — here the
algorithm itself gets to choose where in the timeline an accepted job lands, and that choice
turns out to be exactly as important as which jobs get accepted.
The greedy idea: sort jobs by profit, highest first, and walk the list once. For each job, look for a free slot at or before its deadline — but instead of taking the first free slot you find, scan backward from the deadline itself and take the latest free slot available. If none exists, the job is skipped; it earns nothing. This is the site's fifth entry filed under Greedy, after Huffman Coding, Activity Selection, Fractional Knapsack, and Coin Change. It's also the first of the five where the optimality proof has two independent parts rather than one: sorting by profit is only half the story, and Pitfalls below shows a case where the sort is right but the placement rule is wrong, and profit still comes out short.
Type a list of id/profit/deadline triples (comma-separated), pick a placement rule, and
press Load, then Step or Run. The job chips are
ordered by profit, highest first — a filled accent chip means scheduled (with the slot it landed in
appended), a faded dashed chip means rejected for lack of a free slot. The slot strip below shows every
time unit from 1 up to the largest deadline in the list; a slot getting a bold outline mid-step means the
current job is checking whether that slot is free, and a solid green slot means a job has claimed it. The
demo also brute-forces the true optimal profit for comparison (checked against a different, independent
feasibility rule — see Complexity — capped at 12 jobs so that stays instant), so a rule that leaves profit
on the table is visible immediately, not just claimed.
jobs, sorted by profit (descending)
time slots
Two separate claims need proving, and they don't depend on each other.
Claim 1 — processing jobs highest-profit-first never costs the best job a spot. Let
x be the single highest-profit job overall, with deadline d. Take any optimal
schedule S. If S already runs x, done. If not, look at slot
d in S: either it's empty — but then adding x there strictly
improves S, contradicting optimality — or some other job y occupies it. Since
x has the highest profit of any job, profit(x) ≥ profit(y), so
swapping y out for x at slot d leaves every other slot in
S untouched (still a valid schedule) and loses no profit. So there's always an optimal
schedule that runs x, specifically at slot d. Once x is fixed
there, the remaining problem — best schedule for the rest of the jobs, given slot d is now
occupied — is identical in shape, so the same argument applies again to whichever job is now the
highest-profit one left, and so on. Sorting once and taking a single pass is that induction unrolled.
Claim 2 — once profit order is fixed, "latest available slot" beats every other placement rule. A unit-time job doesn't care when before its deadline it runs, only that it runs by then — every slot from 1 to its deadline is equally good for the job itself. That symmetry is exactly what makes the placement choice free to optimize for the future: giving the current job the latest slot it can still use leaves every earlier slot open for whatever comes next, and an earlier slot can only ever help a job with a tighter deadline, never hurt one with a looser deadline (a looser-deadline job that could have used an early slot can just as well use a later one instead). Taking the earliest available slot instead burns exactly the flexibility a tighter-deadline job — one that hasn't been processed yet, since it's sorted later by profit — might have needed. See Pitfalls for a worked case where that costs real profit.
On the default 5-job set, sorted by profit — P1 (100, due 3), P2 (90, due 1), P3 (80, due 2), P4 (70, due 1), P5 (60, due 3) — the correct rule schedules P1 at slot 3, P2 at slot 1, and P3 at slot 2, for a total profit of 270; P4 and P5 find every slot at or before their own deadline already taken and are skipped. Brute force over all 32 subsets confirms 270 is the true maximum achievable, and confirms no 5-job schedule can do better.
function jobSequencing(jobs) {
// jobs: [{ id, profit, deadline }], deadline >= 1, all unit-time
const sorted = [...jobs].sort((a, b) => b.profit - a.profit);
const maxSlot = Math.max(0, ...jobs.map(j => j.deadline));
const slots = new Array(maxSlot + 1).fill(null); // 1-indexed; slots[0] unused
const scheduled = [];
let totalProfit = 0;
for (const job of sorted) {
for (let t = Math.min(job.deadline, maxSlot); t >= 1; t--) {
if (slots[t] === null) {
slots[t] = job.id;
scheduled.push({ ...job, slot: t });
totalProfit += job.profit;
break;
}
}
}
return { scheduled, totalProfit };
}The placement rule is not a cosmetic detail — it changes the total profit. Switch the demo's rule to earliest available slot on the unchanged default data: P1 (profit 100, due 3) grabs slot 1 the instant it's processed, since slot 1 is the first free slot at or before its own deadline. That looks harmless for P1 — it still gets scheduled — but P2 (profit 90, due 1) comes next and finds its only legal slot, slot 1, already gone. P2 is skipped entirely. The run ends with P1, P3, P5 scheduled for 240 total profit, where the correct rule (and the brute-force optimum, both shown live in the demo) reaches 270 by scheduling P1, P2, P3 instead. Nothing about the profit-descending sort order changed between the two runs — only where P1 was placed — which is exactly Claim 2 above: the earliest slot is never better than the latest one, and here it's strictly worse, because it silently spent a tight-deadline slot on a job that didn't need it yet.
The sort key matters just as much as the placement rule. Paste in the classic
a/100/2, b/19/1, c/27/2, d/25/1, e/15/3 and imagine sorting by profit
ascending instead of descending (this demo always sorts descending, so this is a checked-by-hand,
not directly toggleable, variant): processing lowest-profit-first, e (15) claims slot 3, b (19) claims slot
1, d (25) finds slot 1 taken and is skipped, c (27) claims slot 2, and finally a (100) — the single most
valuable job on the list — finds slots 1 and 2 both taken and its own deadline is 2, so it's skipped too.
Total profit: 61. The correct descending order (verified in the demo by loading that same string) schedules
c, a, and e for 142, confirmed optimal by brute force. Reversing the sort doesn't just reorder who goes
first, it can reject the highest-profit job on the entire list.
This assumes every job takes exactly one time unit. Real scheduling problems often have jobs with different processing times, and once that's true, "does a free slot exist at or before the deadline" stops being a yes/no question answerable by scanning backward from the deadline — a job's duration determines how much contiguous room it needs, not just where it can start. That's a different, harder family of scheduling problems (weighted, variable-length interval scheduling), closer in spirit to Weighted Interval Scheduling's DP than to anything a single greedy pass over unit slots can solve.
Time: sorting is O(n log n); the placement loop then scans, for each of
n jobs, up to min(deadline, n) slots (scheduling more than n jobs is
never possible, so slots beyond the n-th are never useful even if some deadline is larger),
giving O(n²) worst case when deadlines are large — the dominant term over the sort.
Space: O(n) for the sorted copy and the slot array.
This site's own Union-Find page builds a "find the
representative, then reroute everything on the path directly at it" structure for a completely different
purpose (cycle detection in Kruskal). The same reroute-on-find trick, repurposed to mean "find the nearest
free slot at or before this deadline, then remember it," turns the O(n²) scan above into a
near-linear O(n α(n)) one — left out of this demo, since the plain backward scan is
easier to watch happen one slot at a time, but worth knowing the naive version isn't the fastest one
possible.
The demo's brute-force optimal-profit check, shown purely for comparison, tries all 2^n
subsets and tests each for feasibility independently of the greedy algorithm itself — a subset is
schedulable if and only if, for every deadline t, at most t of its jobs have a
deadline of t or earlier (a counting rule, not a simulation of any placement order) — capped at
12 jobs for exactly that reason; nothing about the greedy algorithm needs it.
See Choosing a Greedy Strategy for how this entry's proof compares against the site's other nine Greedy entries — short version: this is Tier 1, exact on every input, but the only one needing two independent exchange arguments (which jobs run, then where they land) instead of one.