This problem is usually called job sequencing with deadlines. Each job takes exactly one unit time slot, has a profit, and must finish by its deadline. That unit-length assumption is what makes the greedy below optimal. It is not the same as weighted interval scheduling, where jobs are intervals of different lengths; that problem needs dynamic programming.
Core idea
You have a set of jobs/tasks/customers, each with:
- a value
- constraint(s) (deadline, duration, resource availability, etc.).
You want to maximize total profit subject to deadlines. The standard greedy approach is:
- Sort jobs by deadline (or group them by deadline).
- Iterate backwards in time (from the last slot to the first).
- At each slot, consider all jobs that could still be scheduled (deadline ≥ current slot).
- Pick the job with maximum profit among those eligible.
- Assign it to the slot, remove it from consideration, and continue.
This is implemented efficiently with a max‑heap (priority queue) to reconcile “time filtration” (deadline constraint) with “profit maximization.”
Proof of Correctness
The proof uses an exchange argument:
- Feasibility:
By construction, each slot gets at most one job, and every job is scheduled at or before its deadline. So the greedy schedule is feasible.
- Optimality:
- Suppose there exists an optimal schedule that differs from the greedy one.
- Consider the latest slot where they differ. The optimal schedule has some job (J), but the greedy picked a job (G) with profit ≥ profit((J)).
- Swap (J) out and put (G) in. This preserves feasibility (since (G)’s deadline ≥ current slot) and does not reduce profit.
- Repeat this process slot by slot. Eventually, the optimal schedule is transformed into the greedy schedule without loss of profit.
- Therefore, the greedy schedule is optimal.
This is the classic deadline scheduling exchange argument: greedy always picks the richest feasible job for each slot, and any deviation can be “repaired” without harm.
Example Problems
Here are problems that can be solved using a general version of this strategy:
- Bank Queue (Kattis): maximize money with deadlines → greedy backwards with heap.
- Job Sequencing with Deadlines (classic): same structure, maximize profit.
- Each job has a profit and deadline; schedule jobs to maximize profit.
- Use a heap‑based greedy solution.
- Interval Scheduling (maximize number of jobs): greedy by earliest finish time.
- Huffman Coding: greedy by merging lowest weights → optimal prefix code.
- Minimum Spanning Tree (Kruskal/Prim): greedy by smallest edge weight → optimal spanning tree.
- Activity Selection: greedy by earliest finish time → maximum set of non‑overlapping activities.
- Task Scheduling with Penalties: greedy by highest penalty first → minimize missed deadlines.
- Each task has a deadline and penalty if late.
- Greedy can minimize penalties by prioritizing tasks with higher penalties earlier.
- Resource allocation in operating systems: Assign processes to CPU slots before deadlines to maximize throughput or minimize missed deadlines.