Job Sequencing Problem

The problem, simply

You get n jobs. Each job takes exactly one unit of time, has a deadline, and pays some profit if it is finished by that deadline. You can do one job at a time, starting at time 0.

Choose which jobs to do and when, so the total profit is as large as possible. Give back two numbers: how many jobs you do, and the total profit.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of jobs. A group can be done if, after sorting it by deadline, the job in position i (counting from 1) has a deadline of at least i. Keep the group with the biggest profit.

1. For each of the 2^n groups, collect its jobs.
2. Sort the group by deadline and check the rule above.
3. If it passes, compare its profit with the best so far.

class Solution {
    // jobs[i] = {id, deadline, profit}
    public int[] jobScheduling(int[][] jobs) {
        int n = jobs.length;
        int bestCount = 0, bestProfit = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            List<int[]> group = new ArrayList<>();
            int profit = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    group.add(jobs[i]);
                    profit += jobs[i][2];
                }
            }
            group.sort((x, y) -> Integer.compare(x[1], y[1]));
            boolean ok = true;
            for (int i = 0; i < group.size(); i++) {
                if (group.get(i)[1] < i + 1) { ok = false; break; } // the hour i+1 is too late
            }
            if (ok && profit > bestProfit) {
                bestProfit = profit;
                bestCount = group.size();
            }
        }
        return new int[]{bestCount, bestProfit};
    }
}

How long it takes: 2^n groups, each sorted in O(n log n), so O(2^n * n log n). Extra room: one group at a time, O(n).

Way 2: the clever way

Follow the chore plan.

1. Sort the jobs by profit, biggest first.
2. Make a row of empty hour slots, one for each hour up to the largest deadline.
3. For each job, look for a free slot starting at its deadline and walking back toward hour 1. Put the job in the first free slot you find.
4. If no slot is free, drop the job.

Why the latest free slot? Putting a job as late as possible keeps the early hours open for jobs with early deadlines. Why biggest profit first? If a big job and a small job fight over the same hours, the big one should win.

class Solution {
    // jobs[i] = {id, deadline, profit}
    public int[] jobScheduling(int[][] jobs) {
        int[][] js = jobs.clone();
        Arrays.sort(js, (x, y) -> Integer.compare(y[2], x[2])); // best pay first

        int maxDeadline = 0;
        for (int[] j : js) maxDeadline = Math.max(maxDeadline, j[1]);
        boolean[] taken = new boolean[maxDeadline + 1];          // hours 1..maxDeadline

        int count = 0, profit = 0;
        for (int[] j : js) {
            for (int hour = j[1]; hour >= 1; hour--) {           // latest free hour first
                if (!taken[hour]) {
                    taken[hour] = true;
                    count++;
                    profit += j[2];
                    break;
                }
            }
        }
        return new int[]{count, profit};
    }
}

How long it takes: sorting is O(n log n). Each job may walk back over up to D hours, where D is the largest deadline, so the total is O(n log n + n * D). Extra room: the hour slots, O(D). Since only n jobs can ever be placed, you can cap D at n.

Way 3: a faster slot finder

The walk back over taken hours is the slow part. Give every hour a sign that says "the nearest free hour at or before me". When an hour gets taken, point its sign at the hour before it. Following signs, and shortening them as you go, finds a free hour in almost constant time. Hour 0 means "nothing free".

class Solution {
    private int[] parent;

    private int find(int h) {                       // nearest free hour at or before h
        if (parent[h] != h) parent[h] = find(parent[h]);
        return parent[h];
    }

    public int[] jobScheduling(int[][] jobs) {
        int n = jobs.length;
        int[][] js = jobs.clone();
        Arrays.sort(js, (x, y) -> Integer.compare(y[2], x[2]));
        parent = new int[n + 1];
        for (int h = 0; h <= n; h++) parent[h] = h;

        int count = 0, profit = 0;
        for (int[] j : js) {
            int free = find(Math.min(j[1], n));     // more than n hours is never needed
            if (free > 0) {
                parent[free] = free - 1;            // this hour is now taken
                count++;
                profit += j[2];
            }
        }
        return new int[]{count, profit};
    }
}

How long it takes: O(n log n) for the sort and nearly O(1) per job after that. Extra room: O(n) for the signs. A very long chain of signs can make the recursion deep, so for huge inputs write find with a loop.

Watch out for

• Sorting by deadline instead of profit gives the most jobs, not the most money.
• Hours start at 1. A deadline of 1 means the job must run in the first hour.
• Deadlines can be larger than n. Cap them at n, or size the slot array by the largest deadline.
• Do not sort the caller's array in place if they need it later. Clone it first.

What interviewers ask next

• Prove the greedy is right. Exchange argument: if a best plan skips the top paying job, it can swap it in for some cheaper job in a slot the top job could use, and the profit does not go down.
• Jobs have different lengths and each must finish by its deadline, and you want to do the most jobs? Sort by deadline, add each job to a max heap of lengths, and when total time passes the deadline, drop the longest job (LeetCode 630, Course Schedule III).
• Jobs have start and end times and a profit? That is weighted interval scheduling: dynamic programming with binary search.
• Can you get the actual schedule? Yes, store the job id in the slot instead of true.

Remember this

Grown-up words: chores are unit time jobs, the hours are time slots, "as late as allowed" keeps early slots for tight deadlines, and the signs pointing to the nearest free hour are a disjoint set union with path compression.