Maximum Profit in Job Scheduling

Hard Dynamic Programming 1D DP Original on LeetCode

Maximum Profit in Job Scheduling is a hard dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (dp + binary search for the next job), runs in O(n log n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (take or skip every job) up.

Problem

There are n jobs. Job i runs from startTime[i] until endTime[i] and pays profit[i] if you do it. You can only work on one job at a time, so the jobs you choose must not overlap. A job that ends at time t does not overlap a job that starts at time t.

Return the largest total profit you can earn by choosing a set of non-overlapping jobs.

Examples

Example 1

Input: startTime = [1, 3, 6, 2], endTime = [4, 7, 9, 6], profit = [30, 25, 40, 20]
Output: 70
Why: Take the job [1, 4) worth 30 and the job [6, 9) worth 40; they do not overlap.

Example 2

Input: startTime = [1, 2, 4, 6, 5], endTime = [3, 5, 6, 9, 8], profit = [20, 20, 70, 60, 10]
Output: 150
Why: Take [1, 3), [4, 6) and [6, 9) for 20 + 70 + 60; a job ending at 6 and a job starting at 6 can both be done.

Example 3

Input: startTime = [1, 1, 1], endTime = [3, 4, 2], profit = [6, 4, 9]
Output: 9
Why: All three jobs start at time 1 and overlap, so only one can be taken; the best is worth 9.

Constraints

1 <= n <= 5 * 10^4, where n is the length of all three arrays.
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (take or skip every job)	`O(2^n · n)`	`O(n)`
Better (bottom-up DP, linear search for the next job)	`O(n²)`	`O(n)`
Optimal (DP + binary search for the next job)	`O(n log n)`	`O(n)`

1Brute force (take or skip every job)

TimeO(2^n · n)Each call can branch into two more calls, and each call scans for the next compatible job.

SpaceO(n)The recursion goes at most n levels deep, plus the sorted copy of the jobs.

Sort the jobs by start time and recurse from the first job. For job i there are two choices: skip it and solve from i + 1, or take it, add its profit and continue from the first job whose start is not before job i's end. Return the better of the two. Without memory, the same subproblems are solved again and again.

Combine the three arrays into jobs and sort them by start time.
solve(i): if i == n return 0.
Find next = the first index j > i with start[j] >= end[i] by scanning.
Return max(solve(i + 1), profit[i] + solve(next)).

class Solution {
    private int[][] jobs;

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[] { startTime[i], endTime[i], profit[i] };
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
        return solve(0);
    }

    private int solve(int i) {
        if (i == jobs.length) return 0;
        int next = i + 1;
        while (next < jobs.length && jobs[next][0] < jobs[i][1]) next++;
        return Math.max(solve(i + 1), jobs[i][2] + solve(next));
    }
}

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(startTime, endTime, profit))
        n = len(jobs)

        def solve(i: int) -> int:
            if i == n:
                return 0
            nxt = i + 1
            while nxt < n and jobs[nxt][0] < jobs[i][1]:
                nxt += 1
            return max(solve(i + 1), jobs[i][2] + solve(nxt))

        return solve(0)

class Solution {
    vector<array<int, 3>> jobs;

    int solve(int i) {
        int n = jobs.size();
        if (i == n) return 0;
        int next = i + 1;
        while (next < n && jobs[next][0] < jobs[i][1]) next++;
        return max(solve(i + 1), jobs[i][2] + solve(next));
    }

public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        jobs.clear();
        for (int i = 0; i < n; i++) jobs.push_back({startTime[i], endTime[i], profit[i]});
        sort(jobs.begin(), jobs.end(), [](const array<int, 3>& a, const array<int, 3>& b) { return a[0] < b[0]; });
        return solve(0);
    }
};

function jobScheduling(startTime, endTime, profit) {
    const n = startTime.length;
    const jobs = [];
    for (let i = 0; i < n; i++) jobs.push([startTime[i], endTime[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    const solve = (i) => {
        if (i === n) return 0;
        let next = i + 1;
        while (next < n && jobs[next][0] < jobs[i][1]) next++;
        return Math.max(solve(i + 1), jobs[i][2] + solve(next));
    };
    return solve(0);
}

2Better (bottom-up DP, linear search for the next job)

TimeO(n²)Each of the n entries may scan up to n jobs to find its next compatible job.

SpaceO(n)The dp array and the sorted jobs hold O(n) values.

The recursion only ever asks for solve(i) with i from 0 to n, so store those answers in dp, filling it from the back: dp[i] is the best profit using only jobs i..n-1 (sorted by start). The next compatible job is still found by a linear scan.

Sort the jobs by start time; dp has n + 1 entries with dp[n] = 0.
For i from n - 1 down to 0: scan for next, the first j > i with start[j] >= end[i].
dp[i] = max(dp[i + 1], profit[i] + dp[next]).
Return dp[0].

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[] { startTime[i], endTime[i], profit[i] };
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int next = i + 1;
            while (next < n && jobs[next][0] < jobs[i][1]) next++;
            dp[i] = Math.max(dp[i + 1], jobs[i][2] + dp[next]);
        }
        return dp[0];
    }
}

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(startTime, endTime, profit))
        n = len(jobs)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            nxt = i + 1
            while nxt < n and jobs[nxt][0] < jobs[i][1]:
                nxt += 1
            dp[i] = max(dp[i + 1], jobs[i][2] + dp[nxt])
        return dp[0]

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<array<int, 3>> jobs;
        for (int i = 0; i < n; i++) jobs.push_back({startTime[i], endTime[i], profit[i]});
        sort(jobs.begin(), jobs.end(), [](const array<int, 3>& a, const array<int, 3>& b) { return a[0] < b[0]; });
        vector<int> dp(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            int next = i + 1;
            while (next < n && jobs[next][0] < jobs[i][1]) next++;
            dp[i] = max(dp[i + 1], jobs[i][2] + dp[next]);
        }
        return dp[0];
    }
};

function jobScheduling(startTime, endTime, profit) {
    const n = startTime.length;
    const jobs = [];
    for (let i = 0; i < n; i++) jobs.push([startTime[i], endTime[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    const dp = new Array(n + 1).fill(0);
    for (let i = n - 1; i >= 0; i--) {
        let next = i + 1;
        while (next < n && jobs[next][0] < jobs[i][1]) next++;
        dp[i] = Math.max(dp[i + 1], jobs[i][2] + dp[next]);
    }
    return dp[0];
}

3Optimal (DP + binary search for the next job)

TimeO(n log n)Sorting costs O(n log n), and each of the n DP steps does one O(log n) binary search.

SpaceO(n)The sorted jobs, the start times and the dp array each hold O(n) values.

Same recurrence, dp[i] = max(dp[i + 1], profit[i] + dp[next(i)]), over jobs sorted by start time. Since the start times are sorted, next(i), the first job starting at or after job i's end, is a lower-bound binary search instead of a scan.

Sort the jobs by start time and copy the start times into a sorted array starts.
dp has n + 1 entries with dp[n] = 0.
For i from n - 1 down to 0: binary search in starts for the first index next with starts[next] >= end[i].
dp[i] = max(dp[i + 1], profit[i] + dp[next]); return dp[0].

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[] { startTime[i], endTime[i], profit[i] };
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
        int[] starts = new int[n];
        for (int i = 0; i < n; i++) starts[i] = jobs[i][0];
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int lo = i + 1, hi = n; // first index with starts[idx] >= end
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (starts[mid] >= jobs[i][1]) hi = mid;
                else lo = mid + 1;
            }
            dp[i] = Math.max(dp[i + 1], jobs[i][2] + dp[lo]);
        }
        return dp[0];
    }
}

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(startTime, endTime, profit))
        n = len(jobs)
        starts = [j[0] for j in jobs]
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            nxt = bisect.bisect_left(starts, jobs[i][1], i + 1, n)
            dp[i] = max(dp[i + 1], jobs[i][2] + dp[nxt])
        return dp[0]

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<array<int, 3>> jobs;
        for (int i = 0; i < n; i++) jobs.push_back({startTime[i], endTime[i], profit[i]});
        sort(jobs.begin(), jobs.end(), [](const array<int, 3>& a, const array<int, 3>& b) { return a[0] < b[0]; });
        vector<int> starts(n);
        for (int i = 0; i < n; i++) starts[i] = jobs[i][0];
        vector<int> dp(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            int next = lower_bound(starts.begin() + i + 1, starts.end(), jobs[i][1]) - starts.begin();
            dp[i] = max(dp[i + 1], jobs[i][2] + dp[next]);
        }
        return dp[0];
    }
};

function jobScheduling(startTime, endTime, profit) {
    const n = startTime.length;
    const jobs = [];
    for (let i = 0; i < n; i++) jobs.push([startTime[i], endTime[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    const starts = jobs.map((j) => j[0]);
    const dp = new Array(n + 1).fill(0);
    for (let i = n - 1; i >= 0; i--) {
        let lo = i + 1, hi = n; // first index with starts[idx] >= end
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (starts[mid] >= jobs[i][1]) hi = mid;
            else lo = mid + 1;
        }
        dp[i] = Math.max(dp[i + 1], jobs[i][2] + dp[lo]);
    }
    return dp[0];
}

Edge cases to test

A job that ends exactly when another starts: both can be taken
A single very profitable long job beats many small ones
Many short jobs beat one long job
Jobs given in no particular order
Only one job

Hints

Hint 1

Sort the jobs by start time. For the first remaining job you either skip it or take it; if you take it, the next job you may consider is the first one starting at or after its end.

Hint 2

That gives best(i) = max(best(i + 1), profit[i] + best(next(i))). The same i is reached many times, so store the answers.

Hint 3

Because the jobs are sorted by start time, next(i) can be found with a binary search instead of a scan.

FAQ

What is the best time complexity for Maximum Profit in Job Scheduling?

Optimal (DP + binary search for the next job) runs in O(n log n) time and O(n) extra space. Sorting costs O(n log n), and each of the n DP steps does one O(log n) binary search.

Which pattern does Maximum Profit in Job Scheduling use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Maximum Profit in Job Scheduling?

Yes. Brute force (take or skip every job) takes O(2^n · n) time and O(n) space. Sort the jobs by start time and recurse from the first job.

Which edge cases should I test for Maximum Profit in Job Scheduling?

A job that ends exactly when another starts: both can be taken; A single very profitable long job beats many small ones; Many short jobs beat one long job; Jobs given in no particular order; Only one job.