Published by Dimitris Kougioumtzis · Updated
Schedule unit-duration jobs in descending profit order, always using the latest free slot before the deadline.
Take profitable unit-duration jobs first and place each in its latest free slot before its deadline.
When to use Job sequencing with deadlines
Reward maximization for unit-length tasks.
Choosing an alternative
Weighted intervals allow arbitrary fixed intervals and need another optimization model.
Worked example: input and state changes
Example input
2,100;1,19;2,27;1,25;3,15
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0 ], "active": [] }Step 2: Place job 2 (profit 27) in slot 1.
State at this checkpoint
{ "values": [ 27, 100, 0 ], "active": [ 0 ], "jobsScheduled": [ 2, 0, -1 ] }Step 3: No free slot before job 3's deadline.
State at this checkpoint
{ "values": [ 27, 100, 0 ], "active": [], "jobsScheduled": [ 2, 0, -1 ] }Step 5: Place job 4 (profit 15) in slot 3.
State at this checkpoint
{ "values": [ 27, 100, 15 ], "active": [ 2 ], "jobsScheduled": [ 2, 0, 4 ] }Step 6: Scheduled profit = 142.
State at this checkpoint
{ "values": [ 27, 100, 15 ], "active": [], "jobsScheduled": [ 2, 0, 4 ], "result": 142 }
Expected final state
Scheduled profit = 142.
Complexity and input bounds
Family: Greedy. Time complexity: O(n²).
Implementation detail: The O(n squared) catalog bound uses the playground condition that deadlines are at most 12. More generally, the direct free-slot scan can cost O(n times D + n squared), where D is the largest deadline.
Space complexity: O(n + maximum deadline) order and slot storage.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1–12 deadline,profit pairs; deadlines 1–12 and profits 0–999.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
The greedy slot rule relies on unit durations; arbitrary lengths cannot be substituted.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // 1–12 unit-duration jobs, deadlines 1–12 and profits 0–999. Returns total profit. output[0] is slot count; following entries are original job indices or -1 for unused slots. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(deadlines, profits, n, output) { let order = Array(256).fill(0); let slots = 0; for (let i = 0; i < n; i++) { order[i] = i; if (deadlines[i] > slots) { slots = deadlines[i]; } } for (let i = 1; i < n; i++) { let j = i; while (j > 0 && profits[order[j - 1]] < profits[order[j]]) { let t = order[j]; order[j] = order[j - 1]; order[j - 1] = t; j--; } } output[0] = slots; for (let i = 1; i <= slots; i++) { output[i] = -1; } let total = 0; for (let i = 0; i < n; i++) { let job = order[i]; let slot = deadlines[job]; while (slot > 0 && output[slot] >= 0) { slot--; } if (slot > 0) { output[slot] = job; total += profits[job]; } } return total; } |
Source
Edmonds provides the matroid/greedy framework relevant to unit-job deadline scheduling, not a claim of first publication of this exact slot implementation.
- Matroids and the greedy algorithm
Jack Edmonds (1971). Related research paper.