Job Scheduling Algo

The problem, simply

You get n jobs. Each job takes exactly one hour, has a deadline d (it must finish by time d), and pays a profit if it is finished in time. You can do only one job at a time, starting at time 0.

Choose which jobs to do and when, so the total profit is as big as possible. Return how many jobs you do and the total profit. Below, D is the biggest deadline.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every set of jobs. A set can be done if, after sorting it by deadline, the first job has a deadline of at least 1, the second at least 2, and so on (the k-th job runs in hour k). Keep the set with the most profit.

import java.util.*;

class Solution {
    public int[] jobScheduling(int[] deadline, int[] profit) {
        int n = deadline.length, bestCount = 0, bestProfit = 0;
        for (int mask = 1; mask < (1 << n); mask++) {          // every set of jobs
            List<Integer> ds = new ArrayList<>();
            int p = 0;
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 1) {
                    ds.add(deadline[i]);
                    p += profit[i];
                }
            }
            Collections.sort(ds);
            boolean fits = true;
            for (int k = 0; k < ds.size(); k++) {
                if (ds.get(k) < k + 1) { fits = false; break; } // job k runs in hour k + 1
            }
            if (fits && p > bestProfit) {
                bestProfit = p;
                bestCount = ds.size();
            }
        }
        return new int[] { bestCount, bestProfit };
    }
}

How long it takes: 2^n sets, each sorted, O(2^n * n log n). Hopeless past about 25 jobs. Extra room: O(n) for one set.

Way 2: the clever way

Be greedy, but in the right way:

1. Sort jobs by profit, biggest first.
2. Keep one box per hour, 1 to D, all free.
3. For each job, look for a free hour starting at its deadline and going earlier. Put the job in the first free hour you find, which is the latest one allowed.
4. If every hour up to its deadline is taken, skip the job.

The bars show each job's allowed time. The boxes are the hours.

import java.util.*;

class Solution {
    public int[] jobScheduling(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) -> profit[b] - profit[a]);    // best paying first

        int maxD = 0;
        for (int d : deadline) maxD = Math.max(maxD, d);
        boolean[] taken = new boolean[maxD + 1];                // hours 1..maxD

        int count = 0, total = 0;
        for (int i : order) {
            for (int h = deadline[i]; h >= 1; h--) {            // latest hour first
                if (!taken[h]) {
                    taken[h] = true;
                    count++;
                    total += profit[i];
                    break;
                }
            }
        }
        return new int[] { count, total };
    }
}

How long it takes: sorting is O(n log n), and each job may scan up to D hours, O(n * D). Extra room: the hour boxes, O(D).

Way 3: jump straight to a free hour

The scan in Way 2 can be slow when many hours are taken. Give every hour a note that says "the latest free hour at or before me". When an hour gets used, its note points one hour earlier. Following notes, and shortening the chain as you go, finds a free hour almost instantly.

import java.util.*;

class Solution {
    int[] note;   // note[h]: latest free hour at or before h, 0 means none

    int find(int h) {
        if (note[h] != h) note[h] = find(note[h]);   // shortcut the chain
        return note[h];
    }

    public int[] jobScheduling(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) -> profit[b] - profit[a]);

        int maxD = 0;
        for (int d : deadline) maxD = Math.max(maxD, d);
        note = new int[maxD + 1];
        for (int h = 0; h <= maxD; h++) note[h] = h;

        int count = 0, total = 0;
        for (int i : order) {
            int h = find(deadline[i]);
            if (h > 0) {                   // a free hour exists
                count++;
                total += profit[i];
                note[h] = h - 1;           // next time, look one hour earlier
            }
        }
        return new int[] { count, total };
    }
}

How long it takes: sorting is O(n log n), and the notes make each lookup nearly constant, so the total is O(n log n). Extra room: O(D), plus the recursion in find (a loop version avoids it).

Watch out for

• Deadlines bigger than n waste room. You never need more than n hours, so cap the hour array at min(D, n) and start each search at min(deadline, n).
• Sorting by deadline instead of profit. That fits many jobs but not the best paying ones.
• Sorting with profit[b] - profit[a] is fine for small profits, but can overflow for huge ones. Integer.compare(profit[b], profit[a]) is always safe.

What interviewers ask next

• Why is greedy correct? Take a best plan that skips the highest paying job. Swap it in for any job that uses an hour it could use: profit does not drop. Repeat this swap for each job in profit order, and you reach the greedy plan.
• What if jobs take different amounts of time and have start and end times? Then it becomes weighted interval scheduling: sort by end time and use dynamic programming with binary search, O(n log n).
• What if jobs have different lengths and deadlines but no profit, and you want to finish as many as possible? Sort by deadline, add each job to a max heap of lengths, and drop the longest job whenever the total time passes the current deadline (LeetCode 630).
• Can you print the plan? Store the job id in each hour instead of a true or false.

Remember this

Grown-up words: this is job sequencing with deadlines, the hour boxes are time slots, best paying first is a greedy choice proved by an exchange argument, and the notes that point to the latest free hour are a disjoint set union with path compression.