Job Sequencing Problem
A medium Greedy interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Greedy
- Sheets
- 3
- Core for
- 3 roles
The problem
There are n jobs, each with a start time, end time, and profit. You can only work on one job at a time and cannot overlap jobs. Find the maximum profit you can achieve.
Example 1
- Input
- startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
- Output
- 120
- Why
- Pick jobs at indices 0 and 3: profit 50+70=120. They don't overlap.
Example 2
- Input
- startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
- Output
- 150
- Why
- Pick jobs at indices 0, 3, and 4: profit 20+70+60=150.
Constraints
- 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
- 1 <= startTime[i] < endTime[i] <= 10^9
- 1 <= profit[i] <= 10^4
How to think about it
Updated 2026-09-29Unlike unweighted interval scheduling where taking the earliest finishing job is always optimal, a job with immense profit might be worth blocking several others. Sorting by end time still provides the right ordering, but decisions require dynamic programming with binary search to locate the latest compatible predecessor.
Approaches, worst first
Recursive search without sorting
time O(2^n) · space O(n)
At each job, test including it and recursively finding subsequent non-overlapping jobs, or skipping it. Recomputes overlapping states exponentially.
Sort by end, scan predecessors
time O(n^2) · space O(n)
Sort jobs by end time. For job i, compute max profit by either taking dp[i-1] or adding job i profit to dp[j], where j is the latest compatible job found by scanning backwards.
Dynamic programming with binary searchWrite this one
time O(n log n) · space O(n)
Sort jobs by end time. For each job, find the latest non-overlapping job using binary search on end times. dp[i] is max(dp[i-1], job.profit + dp[prev]). Each lookup takes logarithmic time, yielding optimal throughput.
Where people lose marks · 3
- Binary search must find the rightmost job where `endTime <= current.startTime`. Using `<` instead of `<=` prevents picking adjacent jobs that start right when another finishes.
- Sorting jobs without keeping startTime, endTime, and profit synchronized across indices.
- Off-by-one indexing when referencing dp values for the binary search predecessor result, particularly when no compatible predecessor job exists.
The theory behind it
Greedy — the ground this problem stands on. All Greedy problems
What Greedy is
A greedy algorithm makes the best-looking choice available right now, at every step, without ever looking back or second-guessing its decision. Think of a cashier making change by handing over the largest possible coin first, repeatedly, until the total is reached. Unlike dynamic programming, which saves and compares answers to multiple overlapping paths, a greedy strategy commits to one immediate option and keeps moving forward.
When to reach for it
Reach for greedy when problems ask for minimum jumps, interval scheduling, assigning resources to maximize satisfaction, or finding fractional values. Key signals include sorted orders where greedily taking the next item never hurts future options, or gas station round trips where running balances prove reachability. If you can prove that taking the immediate best choice never leaves you worse off than any alternative, greedy gives the fastest answer.
How the pattern works
Start by sorting the input to bring the most promising candidates to the front. At each position, evaluate your local rule, take the best available piece, and update your running state. The crucial mental step is proving the greedy choice property: demonstrate that picking this immediate winner cannot block a better global solution down the road. If choosing an item now forces you to reconsider past decisions when conditions change later, greedy fails and you must switch to dynamic programming instead.
More Greedy problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .