Weighted Job Scheduling

The problem, simply

You get n jobs. Each job has a start time, an end time and a profit. You can only do one job at a time, but a job may start exactly when the previous one ends. Choose jobs that do not overlap so the total profit is as big as possible.

Unlike plain activity selection, the jobs pay different amounts, so "do as many jobs as possible" is not the goal.

A story to remember it

Picture it

Examples

Way 1: the simple way

Sort jobs by end time. Let f(i) be the best profit using only the first i jobs.

1. f(0) = 0.
2. Skip job i: f(i - 1).
3. Take job i: its profit plus f(p), where p counts the jobs that end by the time job i starts. Find p by scanning back.
4. f(i) is the bigger of the two.

class Solution {
    int[][] jobs;   // {start, end, profit}

    public int maxProfit(int[] start, int[] end, int[] profit) {
        int n = start.length;
        jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[] {start[i], end[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);        // by end time
        return f(n);
    }

    // best profit using the first i jobs
    private int f(int i) {
        if (i == 0) return 0;
        int skip = f(i - 1);
        int p = i - 1;                                    // jobs that end by the time job i starts
        while (p > 0 && jobs[p - 1][1] > jobs[i - 1][0]) p--;
        int take = jobs[i - 1][2] + f(p);
        return Math.max(skip, take);
    }
}

How long it takes: each call can make two more calls, so up to O(2^n). Extra room: the call chain, O(n).

Way 2: the clever way

Store f(i) in a row best[0..n] and fill it from left to right. To find p fast, use binary search on the end times, which are sorted.

1. Sort the jobs by end time.
2. best[0] = 0.
3. For job i: binary search for p, the number of jobs whose end is at most job i's start.
4. best[i] = max(best[i - 1], profit[i] + best[p]).
5. Return best[n].

class Solution {
    public int maxProfit(int[] start, int[] end, int[] profit) {
        int n = start.length;
        int[][] jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[] {start[i], end[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);          // by end time

        int[] best = new int[n + 1];                         // best[0] = 0
        for (int i = 1; i <= n; i++) {
            int s = jobs[i - 1][0];
            // binary search: how many of the first i-1 jobs end by time s?
            int lo = 0, hi = i - 1;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (jobs[mid - 1][1] <= s) lo = mid; else hi = mid - 1;
            }
            int take = jobs[i - 1][2] + best[lo];
            best[i] = Math.max(best[i - 1], take);           // skip or take
        }
        return best[n];
    }
}

How long it takes: sorting is O(n log n) and each job does one binary search, O(log n), so O(n log n) in all. Extra room: the jobs and the row, O(n).

Watch out for

• Touching ends. A job ending at 3 and one starting at 3 do not overlap here. Use <= in the search. If your problem says they do overlap, use <.
• Greedy picks fail. The most profitable job, the shortest job, or the most jobs can all lose (see the examples).
• Profits can add up past int for big inputs. Use long if needed.

What interviewers ask next

• Print which jobs were chosen. Walk back from best[n]: if best[i] == best[i - 1] the job was skipped, else it was taken and you jump to its p.
• What if all profits are equal? Then it is plain activity selection, and greedy by earliest end time is enough, O(n log n) with no table.
• What if you have k workers instead of one? Add a dimension for how many workers are used, or think of it as a min cost flow problem for big k.
• Can you do it without sorting by end? Sort by start and go from right to left: best[i] = max(best[i + 1], profit[i] + best[next]), where next is the first job starting at or after this one ends. Same O(n log n).

Remember this

Grown-up words: the parties are weighted intervals, sorting by end time sets the DP order, the last job that fits is the latest compatible job, finding it fast is binary search, and the equal profit case is the activity selection problem.