Maximum Profit in Job Scheduling
Given n jobs where every job has a start time, end time, and profit, return the maximum profit without overlapping jobs.
Examples
Take the job ending at 3 for 50 and the one starting at 3 for 70. They touch but do not overlap.
The 100 job runs too long to fit with anything else, so 20 + 70 + 60 wins instead.
All three start at the same time, so only one can be taken — the best-paying one.
Problem Understanding
We have jobs (start, end, profit). We want to pick a subset of non-overlapping jobs to maximize total profit.
Example:
- Job 1: [1, 3], Profit 50
- Job 2: [2, 4], Profit 10
- Job 3: [3, 5], Profit 40
- If we pick Job 1, we can't pick Job 2 (overlap). We CAN pick Job 3.
- Total: 90.
Algorithm Strategy
- Sort the jobs by end time.
dp[i]is then the best profit obtainable from the firstijobs in that order. - For job
ithere are exactly two choices, and together they cover everything:- Leave it: whatever the first
i-1jobs managed —dp[i-1]. - Take it: its profit, plus the best from every job that finishes no later than it starts.
- Leave it: whatever the first
dp[i] = max(take, leave), anddp[n]is the answer.
Why sort by end time? The recurrence needs "the best using only jobs that finish by time t". After sorting by end time, those jobs are always a prefix — so a single index locates the answer in dp.
Why binary search? That prefix's length is exactly the count of jobs ending at or before this job's start, and the end times are sorted, so it is found in O(log n) instead of a backward scan. With n up to 50,000 that is the difference between passing and timing out.
Interactive Visualization
The jobs are drawn in the order the algorithm sorts them — by end time, top to bottom — with dp underneath.
On a search step, every job ending at or before the current job's start is outlined at once. Because of the sort they are always a block from the top, and the size of that block is the dp index the binary search returns. That is the whole trick.
Try Long: three short jobs reach 85 and one long one pays 90, so taking the most jobs loses.
Dry Run
Jobs sorted by End Time:
| Job | [Start, End] | Profit | Prev Compatible | dp logic | Result |
|---|---|---|---|---|---|
| 1 | [1, 3] | 50 | None (0) | max(0, 50+0) |
50 |
| 2 | [2, 4] | 10 | None (0) | max(50, 10+0) |
50 |
| 3 | [3, 5] | 40 | Job 1 (end 3 <= 3) | max(50, 40+50) |
90 |
| 4 | [3, 6] | 70 | Job 1 (end 3 <= 3) | max(90, 70+50) |
120 |
Edge Cases & Common Mistakes
Hard problem nuances:
Sort by end time, not start time. It is what makes the compatible jobs a prefix, and the whole recurrence depends on that.
Touching jobs do not overlap. A job ending at 3 and one starting at 3 can both be taken, which is why the search uses
<=on the start —bisect_right, notbisect_left.O(n²) times out. With n up to 50,000 a backward scan for the last compatible job is too slow; the binary search is what keeps it O(n log n).
Solution
Sort, then one binary search per job — the lines light up as the figure above steps.
Maximum Profit in Job Scheduling Code
1var jobScheduling = function(startTime, endTime, profit) {2 const n = startTime.length;3 const jobs = startTime.map((s, i) => [endTime[i], s, profit[i]]).sort((a, b) => a[0] - b[0]);4 const ends = jobs.map((job) => job[0]);5 const dp = new Array(n + 1).fill(0);6 for (let i = 1; i <= n; i++) {7 const [, start, pay] = jobs[i - 1];8 const idx = upperBound(ends, n, start);9 const include = pay + dp[idx];10 dp[i] = Math.max(include, dp[i - 1]);11 }12 return dp[n];13};1415var upperBound = function(ends, n, start) {16 let lo = 0, hi = n;17 while (lo < hi) {18 const mid = (lo + hi) >> 1;19 if (ends[mid] <= start) lo = mid + 1;20 else hi = mid;21 }22 return lo;23};