Skip to content
doubtly

1 answer

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.

  1. Sort jobs in decreasing order of profit.
  2. Create slots 1 to \(\max d_i\), all empty.
  3. For each job, find the latest empty slot \(\le d_i\). If found, assign the job there; otherwise reject it.

Example.

JobJ1J2J3J4J5
Profit20151051
Deadline22133
  • 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)\).

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.