Job sequencing with deadlines is a greedy method that picks jobs in decreasing order of profit and puts each one in the latest free time slot before its deadline, to maximise total profit.
Problem. There are \(n\) jobs. Job \(i\) has profit \(p_i\) and deadline \(d_i\). Each job takes one unit of time, only one machine is available, and the profit is earned only if the job finishes by its deadline. Find a feasible set of jobs (and their order) with maximum profit.
Greedy algorithm.
- Sort jobs in decreasing order of profit.
- Create slots 1 to \(\max d_i\), all empty.
- For each job, find the latest empty slot \(\le d_i\). If found, assign the job there; otherwise reject it.
Example.
| Job | J1 | J2 | J3 | J4 | J5 |
|---|---|---|---|---|---|
| Profit | 20 | 15 | 10 | 5 | 1 |
| Deadline | 2 | 2 | 1 | 3 | 3 |
- J1 (d = 2) → slot 2.
- J2 (d = 2) → slot 2 is full, so slot 1.
- J3 (d = 1) → slot 1 full → rejected.
- J4 (d = 3) → slot 3.
- J5 (d = 3) → slots 1–3 full → rejected.
Sequence: J2, J1, J4; maximum profit = 15 + 20 + 5 = 40.
Complexity. Sorting takes \(O(n\log n)\); searching for a free slot for each job takes up to \(O(n)\), so the simple version is \(O(n^2)\). Using a disjoint-set (union–find) structure for free slots brings it close to \(O(n\log n)\).