Job Sequencing

Greedy O(n²) O(n)

Schedules deadline-bound unit jobs for maximum profit: greedily place each job (highest profit first) into the latest free hour before its deadline.

Ad≤2+100

Cd≤2+27

Dd≤1+25

Bd≤1+19

Ed≤3+15

hour 1

hour 2

hour 3

Sorted by profit — each job grabs the latest free hour.total0

1/17

Jobs are sorted by profit — most profitable first.

InvariantEach job sits in the latest free hour before its deadline, which keeps earlier hours open for jobs yet to come.

consideringselectedrejected

job-sequencing.c

/* jobs sorted by profit (desc) */
int jobSequence(int dl[], int p[], int n, int maxD) {
    int slot[maxD + 1];
    for (int t = 1; t <= maxD; t++)
        slot[t] = -1;                /* all hours free */
 
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int t = dl[i]; t >= 1; t--) {
            if (slot[t] == -1) {
                slot[t] = i;         /* latest free hour */
                total += p[i];
                break;
            }
        }
    }
    return total;
}

How Job Sequencing works

Highest profit first; put each job into the latest free hour at or before its deadline. Scheduling late keeps earlier hours open for tighter deadlines that may come.

When to use it

Unit-length jobs with deadlines and penalties/profits — maximizing what gets done on time.