What is the optimal solution to Maximum Profit in Job Scheduling?

Weighted Interval Scheduling DP. Sort jobs by end time. Let dp[i] = best profit considering the first i sorted jobs. where p(i) is the largest index j < i such that endTime[j-1] <= startTime[i-1]. Binary search the sorted-end-time array to find p(i).

What is the time complexity of Maximum Profit in Job Scheduling?

Time complexity: O(n log n). Space complexity: O(n).

What are common mistakes on Maximum Profit in Job Scheduling?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Maximum Profit in Job Scheduling

HardAlgorithms

Description

We have `n` jobs, where every job is scheduled to be done from `startTime[i]` to `endTime[i]`, obtaining a profit of `profit[i]`. You're given the `startTime`, `endTime` and `profit` arrays. Return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time `X`, you will be able to start another job that starts at time `X` (i.e., the boundary touches but does not overlap).

Example 1

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output: 120

Explanation: We can take the first and fourth jobs (profit 50 + 70 = 120).

Example 2

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output: 150

Example 3

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]

Output: 6

Constraints

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

Maximum Profit in Job Scheduling: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 5 test cases (2 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Sort jobs by end time.
dp[i] = max profit using jobs[0..i]. For job i, either skip it, or take it and add dp[p(i)] where p(i) is the latest job that ends ≤ start[i].
Use binary search to find p(i) in O(log n).

The optimal approach

Show the approach: Weighted Interval Scheduling DP

Sort jobs by end time. Let `dp[i]` = best profit considering the first `i` sorted jobs.

```

dp[i] = max(dp[i-1], profit[i-1] + dp[p(i)])

```

where `p(i)` is the largest index `j < i` such that `endTime[j-1] <= startTime[i-1]`. Binary search the sorted-end-time array to find `p(i)`.

Time: O(n log n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.