Maximum Profit in Job Scheduling
Maximum Profit in Job Scheduling: jobs have start, end, profit. Pick non-overlapping jobs maximizing total profit (touching endpoints allowed).
- 1 <= startTime.length == endTime.length == profit.length <= 5 * 10⁴
- 1 <= startTime[i] < endTime[i] <= 10⁹
- 1 <= profit[i] <= 10⁴
Intuition
Maximum profit in job scheduling picks non-overlapping jobs to maximise total profit, where each job has a start, an end and a profit. The weights are what make this harder than ordinary interval scheduling.
Without profits, the greedy rule works: sort by end time and take every compatible job, maximising the count. Add profits and that collapses — one long, valuable job can beat several short cheap ones, or vice versa, and no ordering rule decides it in advance. You have to try both.
So it becomes a decision per job: take it or skip it. Sort by end time and let dp[i] be the best profit achievable using the first i jobs.
Skipping is easy — inherit dp[i−1]. Taking job i earns its profit plus the best result among jobs that finish at or before its start. Finding that predecessor by scanning backwards would make the whole thing O(n²), but the ends are sorted:
- Binary search the sorted end times for the last job ending at or before this job's start.
That gives O(log n) per job. The dp array is indexed by job count rather than by time, which keeps it small regardless of how large the timestamps are — worth noting, since a time-indexed table would be infeasible here.
Touching endpoints are allowed, so the search must be inclusive of jobs ending exactly at the start.
Weighted interval scheduling. Unlike the unweighted version, greedy by end time fails — a single high-paying job can beat several cheap ones — so it becomes DP. Sort by end time, and for each job binary search for the last job that finishes before it starts. Sorting to make a binary search possible is the move.
Approach
Before reading on: price up what sorting first costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n log n) time and O(n) space.
See why greedy fails with weights
Unweighted interval scheduling is solved greedily by earliest end time. With profits, one fat job can outweigh many thin ones, so neither earliest-end nor highest-profit ordering is safe — both branches must be evaluated.
Sort jobs by end time
Sorting by end is what makes the predecessor search possible: it puts every candidate predecessor before the current job in the array. Sorting by start would break the binary search entirely.
Define dp over job counts
dp[i] is the best profit using the first i jobs, with dp[0] = 0. Indexing by job count rather than by time keeps the table at size n, which matters because timestamps can reach 10⁹.
Take the better of skip and take
dp[i+1] = max(dp[i], profit[i] + dp[k]) where k is the number of jobs ending at or before job i's start. The first term skips the job, the second takes it — and taking it forfeits every overlapping job automatically.
Binary search for the predecessor
Use bisect_right on the sorted end-time array against the current job's start. Include jobs ending exactly at the start, since the problem permits touching endpoints — using bisect_left here silently rejects valid pairs.
Read the answer from the last cell
dp[n] is the best profit over all jobs. Because each entry already carries the maximum up to that point, no final scan of the table is needed.
Cost of the sorted DP
Sorting is O(n log n) and each of the n jobs does one binary search, giving O(n log n) time overall with O(n) space. Compare with the O(n²) scan for the predecessor — the sort is what pays for itself.
Solution & live demo
Common pitfalls
Greedily taking jobs that end earliest
for e, s, p in sorted(zip(endTime, startTime, profit)):
if s >= last_end: total += p; last_end = edp[i + 1] = max(dp[i], dp[k] + p)
That maximises the count of jobs, not the profit. One job worth 100 beats three worth 1 each, and the greedy has no way to see that — the value has to enter the recurrence.
Searching the whole array rather than the prefix
k = bisect_right(ends, s)
k = bisect_right(ends, s, 0, i)
Without the i bound the search can return a job at or beyond the current one, letting a job depend on itself or on a later job. Only jobs already processed are valid predecessors.
Using bisect_left for the predecessor
k = bisect_left(ends, s, 0, i)
k = bisect_right(ends, s, 0, i)
A job ending exactly when this one starts is compatible — no overlap. bisect_left excludes it and needlessly discards a valid chain.
Edge cases
end ≤ start counts as compatible — bisect_right includes it.
dp keeps the single most profitable one.
dp = [0, profit].