Example 1
ready- Input
startTime = [ 1, 2, 3, 3 ] endTime = [ 3, 4, 5, 6 ] profit = [ 50, 10, 40, 70 ]- Expected
120- Why
- take [1,3) for 50 and [3,6) for 70
Maximum Profit in Job Scheduling
50 min · jobScheduling()A packed calendar isn't necessarily a profitable one. Sometimes skipping a long job makes room for several better jobs.
You're given three equal-length arrays describing n jobs. Job i starts at
startTime[i], ends at endTime[i], and earns profit[i]. Choose non-overlapping jobs
whose total profit is as large as possible, then return that total.
Each job occupies the half-open interval [start, end): it includes its start time
but not its end time. That means a job may start at the exact moment another one ends.
A few ground rules:
- You may take each job at most once.
- Jobs may arrive in any input order.
- You may skip any job; profits are positive, so the best total is always positive.
Constraints
1 <= n <= 50_000startTime.length == endTime.length == profit.length == n1 <= startTime[i] < endTime[i] <= 1_000_000_0001 <= profit[i] <= 10_000- The total of all profits is at most
500_000_000, so every answer fits signed 32-bit.
Hints
Choose a useful order
Sort jobs by end time. Then every job that could come before the current one appears somewhere to its left.
Take it or leave it
Use dynamic programming (DP), which stores answers to smaller prefix problems. For the next job, compare skipping it with taking it after the best compatible prefix.
Find the prefix faster
The sorted end times never decrease. Binary-search for the rightmost earlier job whose end time is at most the current start time; equality must count as compatible.
Follow-up
Could you return the original indices of one optimal set of jobs as well as its profit?
Visible cases
Examples
Example 2
ready- Input
startTime = [ 1, 2, 3, 4, 6 ] endTime = [ 3, 5, 10, 6, 9 ] profit = [ 20, 20, 100, 70, 60 ]- Expected
150- Why
- the jobs [1,3), [4,6), and [6,9) earn 20 + 70 + 60
Example 3
ready- Input
startTime = [ 1, 1, 1 ] endTime = [ 2, 3, 4 ] profit = [ 5, 6, 4 ]- Expected
6- Why
- all three jobs overlap, so choose the most profitable one
Interview signal
Asked at
AmazonGoogle
The hard part isn't choosing a lucrative job. It's knowing which earlier profit remains available once you choose it. Sorting by end time turns that history into a prefix.
After sorting, define dp[i] as the best profit available from the first i jobs. This
is dynamic programming (DP): each prefix answer is reused by later choices.
End-sorted DP + linear scan
For job (start, end, earnings) at sorted index i, there are two choices:
- skip it and keep
dp[i]; - take it, then add its earnings to the best prefix ending no later than
start.
The direct version scans backward to find that compatible prefix. Because intervals are
half-open, previous_end <= start is the correct test.
def job_scheduling(
start_time: list[int],
end_time: list[int],
profit: list[int],
) -> int:
jobs = sorted(zip(start_time, end_time, profit), key=lambda job: job[1])
dp = [0] * (len(jobs) + 1)
for i, (start, _end, earnings) in enumerate(jobs):
compatible_count = 0
for previous in range(i - 1, -1, -1):
if jobs[previous][1] <= start:
compatible_count = previous + 1
break
skip = dp[i]
take = earnings + dp[compatible_count]
dp[i + 1] = max(skip, take)
return dp[-1]Time O(n²) in the worst case because each job may scan every earlier job. Space O(n) for the sorted jobs and DP array.
End-sorted DP + binary search
The end times are sorted, so the backward scan is looking for one cutoff. Use
bisect_right to count earlier end times that are <= start. Limiting the search to
hi=i prevents the current job or any later job from entering its own history.
from bisect import bisect_right
def job_scheduling(
start_time: list[int],
end_time: list[int],
profit: list[int],
) -> int:
jobs = sorted(zip(start_time, end_time, profit), key=lambda job: job[1])
ends = [end for _start, end, _profit in jobs]
dp = [0] * (len(jobs) + 1)
for i, (start, _end, earnings) in enumerate(jobs):
compatible_count = bisect_right(ends, start, hi=i)
skip = dp[i]
take = earnings + dp[compatible_count]
dp[i + 1] = max(skip, take)
return dp[-1]Time O(n log n) for sorting and one binary search per job. Space O(n) for the sorted jobs, end times, and DP array.
The equality handled by bisect_right is easy to miss: a job ending at time 6 is fully
compatible with one starting at time 6.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
120
Run: visible + custom · Submit: full suite