FAANGPrep Sprint
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
SORTED BY END TIME, SO EVERY COMPATIBLE JOB IS A BLOCK FROM THE TOP · OUTLINED = WHAT THE BINARY SEARCH COUNTED
SORT BY END TIME
jobs, sorted by end time
1-3
50
2-4
10
3-5
40
3-6
70
1
6
dp — best profit using the first i jobs
0
1
2
3
4
take it
—
leave it
—
Answer
—
the rule
include = pay[i] + dp[idx]
exclude = dp[i-1]
dp[i] = max(include, exclude)
Sort the 4 jobs by end time: 1-3, 2-4, 3-5, 3-6. With no jobs at all the profit is 0, so dp[0] = 0
Next
Job 1 runs 1 to 3 and pays 50. Take it, or leave it?
jobs
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.