Problem statement

There are n jobs. Job i runs from startTime[i] to endTime[i] and pays profit[i].

Choose a set of jobs in which no two overlap in time, so that the total profit is as large as possible, and return that total. A job that ends at time X does not overlap a job that starts at time X — you may go straight from one to the other.

Example 1

Input: startTime = [1,2,4,6], endTime = [3,5,6,9], profit = [20,30,25,40]
Output: 85
Explanation: Jobs 0, 2 and 3 run back to back (1–3, 4–6, 6–9) for 20 + 25 + 40.

Example 2

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6
Explanation: All three overlap, so only one can be taken.

Example 3

Input: startTime = [1,3,2,5,7], endTime = [4,6,8,9,10], profit = [30,40,90,25,20]
Output: 90

Constraints

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

Hints for Maximum Profit in Job Scheduling

1. Hint 1

   Sort the jobs by end time. Then the best schedule among the first i jobs either skips job i or ends with it.

2. Hint 2

   If it ends with job i, every other chosen job must end by startTime of job i — and those jobs form a prefix of the sorted order.

3. Hint 3

   Let dp[i] be the best profit using the first i jobs in end order. Binary-search the number j of jobs whose end is <= start of job i, and set dp[i] = max(dp[i-1], dp[j] + profit).

How to solve Maximum Profit in Job Scheduling

Weighted interval scheduling. Once jobs are ordered by end time, the jobs compatible with job i that come before it are exactly a prefix of that order — the ones ending no later than job i starts — so a binary search finds where to continue the DP.

Approach

1. Sort job indices by end time; keep the sorted end times in an array ends.
2. dp[0] = 0. For the t-th job in this order (1-based) with start s and profit p:
3. Find j = the number of jobs whose end is <= s (upper bound of s in ends).
4. dp[t] = max(dp[t-1], dp[j] + p) — skip the job, or take it after the best schedule of the first j jobs.
5. Return dp[n].

Why it works

Consider an optimal schedule of the first t jobs. If it does not use job t, its value is dp[t-1]. If it does, the other jobs end by s, and any job ending by s ends strictly before job t does, so they all lie among the first j jobs; conversely every one of those first j jobs is compatible with job t. The best way to use them is dp[j], so the recurrence covers both cases exactly.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Touching endpoints are allowed: search for ends <= start, not < start.
• Sort by end time; sorting by start breaks the prefix property the binary search relies on.
• Greedy choices (most profitable first, earliest end first) both fail on weighted jobs.

Reference solution

Python

from typing import List
from bisect import bisect_right

def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    n = len(startTime)
    order = sorted(range(n), key=lambda i: endTime[i])
    ends = [endTime[i] for i in order]
    dp = [0] * (n + 1)
    for t in range(1, n + 1):
        i = order[t - 1]
        j = bisect_right(ends, startTime[i])
        dp[t] = max(dp[t - 1], dp[j] + profit[i])
    return dp[n]

Java

public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int n = startTime.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(endTime[a], endTime[b]));
    int[] ends = new int[n];
    for (int i = 0; i < n; i++) ends[i] = endTime[order[i]];
    int[] dp = new int[n + 1];
    for (int t = 1; t <= n; t++) {
        int i = order[t - 1], s = startTime[i];
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (ends[mid] <= s) lo = mid + 1; else hi = mid;
        }
        dp[t] = Math.max(dp[t - 1], dp[lo] + profit[i]);
    }
    return dp[n];
}

C++

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = startTime.size();
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return endTime[a] < endTime[b]; });
    vector<int> ends(n);
    for (int i = 0; i < n; i++) ends[i] = endTime[order[i]];
    vector<int> dp(n + 1, 0);
    for (int t = 1; t <= n; t++) {
        int i = order[t - 1];
        int j = upper_bound(ends.begin(), ends.end(), startTime[i]) - ends.begin();
        dp[t] = max(dp[t - 1], dp[j] + profit[i]);
    }
    return dp[n];
}

JavaScript

var jobScheduling = function(startTime, endTime, profit) {
    var n = startTime.length;
    var order = [];
    for (var i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return endTime[a] - endTime[b]; });
    var ends = order.map(function(i) { return endTime[i]; });
    var dp = new Array(n + 1).fill(0);
    for (var t = 1; t <= n; t++) {
        var i = order[t - 1], s = startTime[i];
        var lo = 0, hi = n;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (ends[mid] <= s) lo = mid + 1; else hi = mid;
        }
        dp[t] = Math.max(dp[t - 1], dp[lo] + profit[i]);
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard