☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Job sequencing Problem

Medium TUF ID 547 A2ZSDE

Java source ↗ Edit this article ↗

Problem

You are given n jobs. Job i has a deadline deadline[i] and a profit profit[i]. Every job takes exactly one unit of time, the machine runs one job at a time, and the clock starts at 0. A job earns its profit only if it finishes no later than its deadline, so a job with deadline d must occupy one of the unit slots ending at times 1, 2, ..., d. Choose which jobs to run, and when, so that the total profit is as large as possible. Return two numbers: how many jobs are done and the maximum total profit.

Constraints (GfG version): 1 ≤ n ≤ 10^5, 1 ≤ deadline[i] ≤ n, 1 ≤ profit[i] ≤ 500. The code below also accepts deadlines larger than n.

Because every profit is positive, the job count is well defined: the sets of jobs that can all meet their deadlines have an exchange property (they form a matroid), so every maximum-profit set has the same size.

Example 1

deadline = [4, 1, 1, 1], profit = [20, 10, 40, 30]
answer = [2, 60]

Three jobs share deadline 1, and only one of them can use slot 1, so take the one worth 40. The deadline-4 job (20) fits in any later slot.

Example 2

deadline = [2, 1, 2, 1, 1], profit = [100, 19, 27, 25, 15]
answer = [2, 127]

No job may finish after time 2, so at most two jobs run. The best pair is 100 + 27, for example 27 in slot 1 and 100 in slot 2.

Approach 1: Brute force

Intuition. The answer is some subset of the jobs, so try every subset and keep the most profitable one that can actually be scheduled. Checking one subset is easy if you run its jobs in order of deadline: the k-th job in that order finishes at time k, so the subset is feasible exactly when the k-th smallest deadline is at least k for every k. Earliest-deadline-first is the right test because if any order works, swapping two neighbours that are out of deadline order still works: the job with the earlier deadline moves earlier, and the other one moves into a slot that ends no later than the earlier deadline, which is no later than its own.

Algorithm.

  1. For every bitmask mask from 0 to 2^n - 1, collect the deadlines of the chosen jobs and their total profit.
  2. Sort the chosen deadlines. If some chosen[k] < k + 1, the subset is infeasible.
  3. Keep the feasible subset with the largest profit (on a profit tie, prefer more jobs).
static int[] bruteForce(int[] deadline, int[] profit) {
    int n = deadline.length;
    int bestCount = 0, bestProfit = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> chosen = new ArrayList<>();
        int total = 0;
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) {
                chosen.add(deadline[i]);
                total += profit[i];
            }
        }
        Collections.sort(chosen);                                  // earliest deadline first
        boolean feasible = true;
        for (int k = 0; k < chosen.size(); k++) {
            if (chosen.get(k) < k + 1) {                           // the (k+1)-th job finishes at time k+1
                feasible = false;
                break;
            }
        }
        if (feasible && (total > bestProfit || (total == bestProfit && chosen.size() > bestCount))) {
            bestProfit = total;
            bestCount = chosen.size();
        }
    }
    return new int[]{bestCount, bestProfit};
}

Complexity. Time O(2^n · n log n): 2^n subsets, each collected and sorted. Space O(n) for the chosen list. Fine for n ≤ 20 as a checker, hopeless for 10^5.

Approach 2: Better, greedy by profit into the latest free slot

Intuition. Two greedy decisions make this fast.

Most profitable first. Let J be the most profitable job, with deadline d. Take any optimal schedule that does not contain J. If one of the slots 1..d is empty, putting J there adds profit, a contradiction. Otherwise all of 1..d are occupied, and replacing any of those jobs by J cannot lower the profit. Either way some optimal schedule contains J, so we can commit to it and repeat the argument on the rest.

As late as possible. When a job is accepted, put it in the latest free slot that still meets its deadline. Early slots are the scarce ones, since every job can use slot 1 but only long-deadline jobs can use slot 10. Taking a late slot keeps the early ones open for jobs with tight deadlines that come later in profit order. Putting it in the earliest free slot fails on deadline = [2, 1], profit = [50, 40]: the 50 job would take slot 1 and the 40 job would have nowhere to go, giving 50 instead of 90.

With the latest-slot rule, a job is rejected only when the jobs already accepted genuinely leave no room for it, so the greedy never throws away a job that could have fitted.

Algorithm.

  1. Sort job indices by profit, highest first.
  2. Make a used array of slots 1..maxDeadline.
  3. For each job, scan t from its deadline down to 1; take the first free slot, add the profit and count it. If no slot is free, skip the job.
static int[] better(int[] deadline, int[] profit) {
    int n = deadline.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(profit[b], profit[a]));   // descending profit
    int maxDeadline = 0;
    for (int d : deadline) maxDeadline = Math.max(maxDeadline, d);
    boolean[] used = new boolean[maxDeadline + 1];                         // used[t]: the slot ending at time t is taken
    int count = 0, total = 0;
    for (int i : order) {
        for (int t = deadline[i]; t >= 1; t--) {
            if (!used[t]) {
                used[t] = true;
                count++;
                total += profit[i];
                break;
            }
        }
    }
    return new int[]{count, total};
}

Dry run on example 1 (jobs sorted by profit):

profit deadline slots tried result slots taken
40 1 1 take slot 1 {1}
30 1 1 (taken) skip {1}
20 4 4 take slot 4 {1, 4}
10 1 1 (taken) skip {1, 4}

Two jobs, profit 60.

Complexity. Time O(n log n + n · D) where D is the largest deadline: the sort, then for each job a scan of at most D slots. Space O(n + D) for the index order and the slot array. When all n jobs have deadline n, the scans have lengths 1, 2, ..., n, which is O(n^2) in total.

Approach 3: Optimal, disjoint set for “latest free slot”

Intuition. The greedy is already right; only the inner scan is slow. What we need is a structure that answers “largest free slot at or below d” and supports “mark this slot taken”. A disjoint set union does exactly that. Each slot starts as its own root, meaning “I am free”. When slot t is taken, point it at t - 1. Now find(d) follows pointers down to the first free slot, and path compression rewrites every visited pointer to land directly on that answer, so a long run of taken slots is skipped in one hop next time. Slot 0 is a sentinel root meaning “nothing left”.

There is also a small saving on memory: with n jobs at most n slots can ever be used, so a deadline larger than n can be capped at n without changing the answer. The DSU therefore needs only n + 1 entries regardless of how large the deadlines are.

Algorithm.

  1. Sort job indices by profit, highest first.
  2. Initialise parent[t] = t for t = 0..n.
  3. For each job, slot = find(min(deadline, n)). If slot > 0, take it: set parent[slot] = slot - 1, add the profit and count it.
static int[] optimal(int[] deadline, int[] profit) {
    int n = deadline.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(profit[b], profit[a]));
    int[] parent = new int[n + 1];                                         // find(t) = latest free slot <= t, 0 = none
    for (int t = 0; t <= n; t++) parent[t] = t;
    int count = 0, total = 0;
    for (int i : order) {
        int slot = find(parent, Math.min(deadline[i], n));                // n jobs never need more than n slots
        if (slot > 0) {
            parent[slot] = slot - 1;                                       // slot taken: point it at the one before
            count++;
            total += profit[i];
        }
    }
    return new int[]{count, total};
}

static int find(int[] parent, int t) {
    int root = t;
    while (parent[root] != root) root = parent[root];
    while (parent[t] != root) {
        int next = parent[t];
        parent[t] = root;
        t = next;
    }
    return root;
}

The find is iterative on purpose. If jobs with deadlines 1, 2, ..., n - 1 happen to come first in profit order, each takes its own slot without any find walking a chain, which leaves the pointers n-1 → n-2 → ... → 0. A later job with deadline n - 1 then walks a chain of length about n before compression kicks in, and a recursive find that deep risks a stack overflow in Java.

Complexity. Time O(n log n): the sort dominates, and the DSU work is O(log n) amortised per find with path compression alone (practically constant). Space O(n) for the order array and parent.

A different O(n log n) route uses a min-heap: process jobs by increasing deadline, push each profit, and whenever the heap holds more jobs than the current deadline allows, pop the smallest profit. It reaches the same answer; the DSU version is shown here because it follows the classic greedy directly.

Edge cases and pitfalls