Job Sequencing with Deadlines

Each job has a deadline and a profit, and takes one time unit. Schedule as many jobs as possible before their deadlines to maximize total profit. The greedy solution sorts by profit and places each job in the latest available slot on or before its deadline. This lesson covers the algorithm, proof sketch, and implementations in C, Java, and Python with trace tables.

Overview

You have a single machine that runs one job per day (or hour). Job J must finish by day deadline[J] and earns profit[J]. You cannot run two jobs on the same day. Which jobs should you pick?

Jobs (deadline, profit):
  J1:(2,100)  J2:(1,19)  J3:(2,27)  J4:(1,25)  J5:(3,15)

Greedy (sort by profit desc):
  J1 → slot 2,  J3 → slot 1,  J5 → slot 3  (skip J4, J2)

Schedule: day1=J3, day2=J1, day3=J5  →  max profit = 142

Problem Statement

Input: n jobs; each job i has deadline d[i] and profit p[i]. Each job duration = 1 unit.

Output: Maximum total profit from a subset of jobs schedulable within their deadlines (at most one job per time slot).

Feasibility: If job i is assigned to time slot t, then 1 ≤ t ≤ d[i] and no other job uses slot t.

Complexity target: O(n log n) for sorting + O(n × max_deadline) with slot array, or O(n log n) with union-find for slot search.

Greedy Algorithm

1. Sort jobs by decreasing profit.
2. Let maxD = maximum deadline; create slots 1 … maxD (initially empty).
3. For each job in sorted order:
   • From t = deadline down to 1, find the latest empty slot.
   • If found, assign the job to slot t and add its profit.
   • Otherwise skip the job.

Why Greedy Works

Exchange argument (sketch): Let jobs be processed in profit order. If the greedy schedule rejects a high-profit job while a lower-profit job occupies an earlier slot that could be shifted, swap assignments without violating deadlines — total profit does not decrease. Greedy always picks the highest-profit job that can still fit; any optimal solution can be transformed to match greedy choices one job at a time.

Code (C, Java, Python)

Python

def job_sequencing(jobs):
    """Max profit job sequencing — sort by profit, latest free slot. O(n log n + n*D)."""
    jobs = sorted(jobs, key=lambda x: x[1], reverse=True)  # (deadline, profit)
    max_deadline = max(d for d, _ in jobs)
    slots = [None] * (max_deadline + 1)
    total_profit = 0
    scheduled = []

    for deadline, profit in jobs:
        for t in range(deadline, 0, -1):
            if slots[t] is None:
                slots[t] = (deadline, profit)
                total_profit += profit
                scheduled.append(t)
                break

    return total_profit, slots


if __name__ == "__main__":
    jobs = [(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]
    profit, slots = job_sequencing(jobs)
    print(f"max profit = {profit}, slots = {slots}")  # 142

Java

import java.util.Arrays;
import java.util.Comparator;

public class JobSequencing {

    /** Sort by profit desc; assign each job to latest free slot before deadline. */
    public static int maxProfit(int[][] jobs) {
        Arrays.sort(jobs, Comparator.comparingInt(a -> -a[1])); // profit desc
        int maxD = 0;
        for (int[] j : jobs) maxD = Math.max(maxD, j[0]);

        int[] slots = new int[maxD + 1]; // 0 = free, else profit stored
        int total = 0;

        for (int[] job : jobs) {
            int deadline = job[0], profit = job[1];
            for (int t = deadline; t >= 1; t--) {
                if (slots[t] == 0) {
                    slots[t] = profit;
                    total += profit;
                    break;
                }
            }
        }
        return total;
    }

    public static void main(String[] args) {
        int[][] jobs = {{2, 100}, {1, 19}, {2, 27}, {1, 25}, {3, 15}};
        System.out.println(maxProfit(jobs)); // 142
    }
}

C

#include <stdio.h>
#include <stdlib.h>

typedef struct { int deadline, profit; } Job;

int cmp_profit_desc(const void *a, const void *b) {
    return ((Job *)b)->profit - ((Job *)a)->profit;
}

int job_sequencing(Job jobs[], int n) {
    qsort(jobs, n, sizeof(Job), cmp_profit_desc);
    int maxD = 0, i, t, total = 0;
    for (i = 0; i < n; i++)
        if (jobs[i].deadline > maxD) maxD = jobs[i].deadline;

    int *slots = (int *)calloc(maxD + 1, sizeof(int)); /* 0 = free */

    for (i = 0; i < n; i++) {
        for (t = jobs[i].deadline; t >= 1; t--) {
            if (slots[t] == 0) {
                slots[t] = 1;
                total += jobs[i].profit;
                break;
            }
        }
    }
    free(slots);
    return total;
}

int main(void) {
    Job jobs[] = {{2, 100}, {1, 19}, {2, 27}, {1, 25}, {3, 15}};
    printf("%d\n", job_sequencing(jobs, 5)); /* 142 */
    return 0;
}

Output & Trace

Input jobs

Greedy scheduling trace

Final schedule & program output

Finding Free Slots Efficiently

Scanning slots from deadline down to 1 costs O(max_deadline) per job. For large deadlines, use Disjoint Set Union (Union-Find):

• Maintain parent[t] pointing to the latest free slot ≤ t.
• find(t) returns the greatest available slot on or before t.
• After assigning slot t, union it with t - 1.

This reduces slot lookup to nearly O(1) amortized per job, giving overall O(n log n) when dominated by sorting.

Variants & Related Problems

Approach Comparison

Real-Life Applications

Interview Tips

1. Confirm: each job takes one unit and only one job runs per slot.
2. State algorithm: sort by profit descending, assign to latest free slot ≤ deadline.
3. Walk through a 4–5 job trace — interviewers expect the slot-filling table.
4. If max_deadline is huge, mention Union-Find optimization.
5. Contrast with activity selection (max count, finish-time sort) vs this problem (max profit, deadline slots).
6. For varying job lengths, say weighted interval scheduling needs DP, not this greedy.