Unit-Time Job Sequencing with Deadlines

Each job takes one time slot, has an integer deadline $d_j$, and earns nonnegative profit $p_j$ only if completed by that deadline. Choose and schedule jobs to maximize total profit on one machine.

These unit-time and deadline assumptions are part of the problem; arbitrary durations require a different scheduling model.

Greedy rule

Process jobs by descending profit. Put each job into the latest still-empty slot no later than its deadline. Scheduling late preserves earlier slots for jobs with tighter deadlines.

sort jobs by decreasing profit
for each job:
    scan backward from min(deadline, number_of_jobs)
    place it in the first empty slot found

Why the choice works

The feasible sets of unit jobs satisfy an exchange structure: when a profitable job is accepted, moving it to its latest feasible slot leaves maximum room for the remaining jobs. A schedule can be exchanged into this form without reducing profit.

Cost and improvements

• Sorting costs $O(n\log n)$.
• A direct backward slot scan can cost $O(nD)$, bounded by $O(n^2)$ after capping useful deadlines at $n$.
• A disjoint-set structure can locate the latest available slot efficiently, making sorting the dominant term in common implementations.

Zero or negative-profit jobs should not be scheduled merely to fill space when jobs are optional.

Source

• GeeksforGeeks: Job Sequencing Problem