Job scheduling

Dec 7, 2025

Updated 1 day ago

6 min read

Job Scheduling — Why Greed Actually Wins Here (And When It Doesn't)

Most articles give you the sorted table and the answer. This one explains why sorting by profit is the right move — not just that it is.

Here's a question nobody asks in class: why does picking the most profitable job first actually work?

Greedy algorithms have this reputation of being "obviously correct" — and that reputation makes students stop thinking. You sort, you pick, you move on. But greedy algorithms fail constantly on problems that look identical to this one. The Fractional Knapsack works greedily. The 0/1 Knapsack doesn't. Both involve picking items with values and constraints.

So what's special about job scheduling? Why does greed give the optimal answer here, and not just a good approximation?

That's what this note is actually about.

The Problem

You have m jobs: $J_{1}, J_{2}, \dots, J_{m}$ .

Each job has:

A deadline $D_{i}$ — the job must be completed at or before this time slot
A profit $P_{i}$ — earned only if the job is completed within its deadline

Assumptions:

Each job takes exactly 1 time unit
Only one job can run per time slot
A job either completes fully (earning full profit) or is skipped (earning nothing)

Objective: Schedule a subset of jobs to maximize total profit, subject to all deadline constraints being met.

The Example

Job	Deadline	Profit
J1	1	150
J2	2	200
J3	1	120
J5	2	90
J4	3	60

Maximum deadline = 3, so we have 3 time slots: [1], [2], [3].

We can schedule at most 3 jobs total, but deadline constraints will tighten this further.

Why Greedy Works Here — The Proof Sketch

Before we run the algorithm, let's understand why it's correct.

Greedy Choice Property: Suppose an optimal schedule exists that does not include the highest-profit job $J_{k}$ . We claim we can always swap in $J_{k}$ without reducing profit.

$J_{k}$ has some deadline $D_{k}$
If any slot $\leq D_{k}$ is free in the optimal schedule, we add $J_{k}$ there — profit goes up
If all slots $\leq D_{k}$ are filled, we find the job $J_{x}$ in those slots with the lowest profit. Since $J_{k}$ is the highest-profit unscheduled job, $P_{k} \geq P_{x}$ . Swap $J_{x}$ with $J_{k}$ — profit doesn't decrease

In both cases, including $J_{k}$ never makes things worse. So any optimal solution can be transformed to include the greedy choice — which means the greedy choice is safe.

This is called the exchange argument — it's the standard proof technique for greedy correctness. Once you've seen it here, you'll recognize it in Huffman coding, activity selection, and MST proofs too.

The Algorithm

plaintext

JobScheduling(jobs):
    Sort jobs in decreasing order of profit
    Initialize slots[1..max_deadline] = empty
    result = []

    for each job J in sorted order:
        for t = J.deadline down to 1:
            if slots[t] is empty:
                slots[t] = J
                result.add(J)
                break

    return result

Key detail: we try to place each job as late as possible within its deadline. This is called the latest-slot-first strategy, and it's deliberate — placing a job early wastes a slot that an earlier-deadline job might desperately need.

Full Trace

Step 1: Sort by profit descending.

Job	Deadline	Profit
J2	2	200
J1	1	150
J3	1	120
J5	2	90
J4	3	60

Slots available: [1] [ ] , [2] [ ] , [3] [ ]

Process J2 (deadline 2, profit 200):

Try slot 2 → free → assign J2 to slot 2 ✓

Slots: [1] [ ] , [2] [J2] , [3] [ ]

Process J1 (deadline 1, profit 150):

Try slot 1 → free → assign J1 to slot 1 ✓

Slots: [1] [J1] , [2] [J2] , [3] [ ]

Process J3 (deadline 1, profit 120):

Try slot 1 → occupied by J1
No earlier slots available → J3 skipped ✗

Process J5 (deadline 2, profit 90):

Try slot 2 → occupied by J2
Try slot 1 → occupied by J1
No slots available → J5 skipped ✗

Process J4 (deadline 3, profit 60):

Try slot 3 → free → assign J4 to slot 3 ✓

Slots: [1] [J1] , [2] [J2] , [3] [J4]

Final Schedule:

Time Slot	Job	Profit
1	J1	150
2	J2	200
3	J4	60

Total Profit = 150 + 200 + 60 = 410

Jobs scheduled: {J1, J2, J4} — J3 and J5 are dropped.

Why J3 and J5 Are Dropped (Intuition Check)

J3 has deadline 1 — it must run in slot 1. But J1 also has deadline 1 and higher profit. Both can't fit, so J3 goes.

J5 has deadline 2 — it can run in slot 1 or 2. Both are taken by higher-profit jobs. So J5 goes too.

Notice: we didn't arbitrarily skip them. The algorithm tried to fit them — it just couldn't find a valid slot. That's the algorithm being honest about constraints, not greedy being sloppy.

Complexity Analysis

	Complexity
Sorting	$O (m lo g m)$
Slot assignment (naive)	$O (m \times d_{ma x})$
Slot assignment (with Union-Find)	$O (m lo g m)$
Space	$O (d_{ma x})$

The naive slot assignment loops over deadlines for each job — $O (m \cdot d)$ in the worst case. For large inputs, you can replace it with a Disjoint Set Union (DSU) structure that finds the latest free slot in near $O (1)$ amortized — bringing the total to $O (m lo g m)$ .

For exam purposes, the naive version is expected. For competitive programming, DSU is the move.

Greedy vs. DP — When Does Greedy Fail?

This is worth pausing on.

Job scheduling (unit time, maximize profit) → Greedy works ✓

What if jobs had variable durations? Say J1 takes 3 hours and J2 takes 1 hour, and you have a 4-hour window. Greedy by profit might schedule J1 (3h, profit 200) and skip J2 (1h, profit 150) + J3 (1h, profit 100) — missing a total of 250 for 200.

That's the weighted job scheduling problem → Greedy fails, DP required.

The unit-time assumption is what makes the exchange argument watertight. Once jobs have different lengths, swapping them changes the feasibility of the entire schedule, not just one slot. Greedy loses its guarantee.

Knowing why greedy works also tells you exactly where it breaks.

Quick Self-Test

Q1: Why do we assign jobs to the latest available slot rather than the earliest?
Q2: In the example, what's the maximum possible profit if we had unlimited time slots?
Q3: Would the answer change if J4's deadline was 1 instead of 3?
Q4: What property of this problem makes the greedy exchange argument valid?

(Answers: Placing jobs late preserves early slots for jobs that can't go anywhere else. 150+200+120+90+60 = 620 — but deadlines make that impossible. Yes — J4 would compete with J1 and J3 for slot 1, and with profit 60 it would be displaced, reducing total to 350. The unit-time assumption ensures any two jobs can be swapped in the schedule without breaking feasibility elsewhere.)

Greedy Approach for Algorithm Design — the general framework: greedy choice property + optimal substructure
Fraction Knapsack — another greedy-correct problem; compare why it works vs 0/1
Dynamic Programming & 0/1 Knapsack — what happens when greedy fails and DP takes over
MST: Kruskal's & Prim's — greedy on graphs; exchange argument reappears in the correctness proof
Dijkstra's Algorithm — greedy shortest path; see the same "locally optimal, globally correct" pattern
Asymptotic Notation — for reading O(m log m) and O(m·d) properly
Algorithm Basics — correctness, termination, and what makes an algorithm provably right
Tower of Hanoi — the other classic in this series; recursion vs greedy thinking
Full DAA Notes Index

External References

Greedy Algorithms — CLRS Chapter 16 — formal proof of greedy correctness via matroid theory
CP-Algorithms: Scheduling Jobs — competitive programming variants including weighted job scheduling
Weighted Job Scheduling (DP approach) — GFG — for when greedy fails and you need DP
Visualgo — no dedicated job scheduling visual, but the sorting and greedy modules build the same intuition

Part of the DAA Design and Analysis series on NoteHub.