On this page
Description
You have jobs with start times, end times and profits, and you can work on only one job at a time. Which jobs maximize the total profit? If every job paid the same, a greedy rule would do: always pick the job that ends earliest. With profits, that fails, because one long, valuable job can beat several short ones. The fix is a take-or-skip DP over jobs sorted by end time, with a binary search for the last job that finishes in time.
We'll go from simple to more technical:
- The pattern: sort by end, then best[i] = max(skip, profit + best[last compatible]).
- A second flavor: a DP over positions when times are small integers.
- Where weighted scheduling shows up (bookings, ad slots, rides).
- What breaks it: greedy rules, strict comparisons, linear scans, overflow.
The approach
Java
int jobScheduling(int[] start, int[] end, int[] profit) {
int n = start.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(end[a], end[b])); // by end time
int[] ends = new int[n];
for (int i = 0; i < n; i++) ends[i] = end[order[i]];
int[] best = new int[n + 1]; // best[i] = max profit using the first i jobs (by end)
for (int i = 1; i <= n; i++) {
int job = order[i - 1];
int k = lastEndingBy(ends, i - 1, start[job]); // how many earlier jobs end at or before this start
best[i] = Math.max(best[i - 1], // skip this job
best[k] + profit[job]); // take it, after the compatible ones
}
return best[n];
}
// number of jobs among ends[0..limit) whose end <= t (ends is sorted)
int lastEndingBy(int[] ends, int limit, int t) {
int lo = 0, hi = limit;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (ends[mid] <= t) lo = mid + 1; else hi = mid;
}
return lo;
}
Python
from bisect import bisect_right
def job_scheduling(start: list[int], end: list[int], profit: list[int]) -> int:
jobs = sorted(zip(end, start, profit)) # by end time
ends = [e for e, _, _ in jobs]
best = [0] * (len(jobs) + 1) # best[i] = max profit using the first i jobs (by end)
for i in range(1, len(jobs) + 1):
_, s, p = jobs[i - 1]
k = bisect_right(ends, s, 0, i - 1) # how many earlier jobs end at or before this start
best[i] = max(best[i - 1], # skip this job
best[k] + p) # take it, after the compatible ones
return best[-1]
Sorted by end time, the jobs compatible with job i - those ending by its start - form a prefix of the list, so "the best I can do before this job starts" is just best[k] for the length k of that prefix, found by binary search. In Python that search is one call: bisect.bisect_right(ends, start, 0, i - 1) counts the ends <= start (bisect_left would count only those < start). <= makes a job that ends exactly when another starts compatible, as the problem defines.
A second flavor: DP over positions
When jobs (or rides, bookings) live on a small range of integer positions, you don't need sorting or binary search at all. Walk positions from right to left: at each point, either move on, or take a job that starts here and jump to its end.
Java
long[] best = new long[n + 2]; // best[p] = most you can still earn from point p
for (int p = n - 1; p >= 1; p--) {
best[p] = best[p + 1]; // nothing starts here (or skip it)
for (int[] r : startingAt.get(p)) // rides {start, end, tip} beginning at p
best[p] = Math.max(best[p], (long) (r[1] - r[0]) + r[2] + best[r[1]]);
}
return best[1];
Python
best = [0] * (n + 2) # best[p] = most you can still earn from point p
for p in range(n - 1, 0, -1):
best[p] = best[p + 1] # nothing starts here (or skip it)
for start, end, tip in starting_at[p]: # rides beginning at p
best[p] = max(best[p], (end - start) + tip + best[end])
That's O(positions + jobs). This is also why "sort by start time" is not wrong in itself: with jobs sorted by start, a DP from the right (take job i and jump to the first job starting at or after its end, or skip it) is equally correct. What must match is the sort order and the direction of the recurrence.
Where you'll see it
Booking systems that must accept or reject overlapping requests for a single resource (a room, a machine, a broadcast slot) to maximize revenue, ad-slot and spectrum auctions, and ride-dispatch problems like the taxi example are weighted interval scheduling. When the timeline is discretized (minutes in a day, days in a season), the positions version is simpler and faster.
Which tool for which job?
| You need | Use |
|---|---|
| Max profit, one worker | sort by end, take or skip, binary search for the last compatible job |
| Times are small integers | a DP over positions from right to left |
| Max number of jobs, no profits | the earliest-end greedy, provably optimal |
| Which jobs were chosen | walk the table back |
| Two or more workers | not this DP run twice: min-cost flow, or a DP over pairs |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Greedy by earliest end | 20 instead of 100 | DP when profits differ |
| Greedy by highest profit | 50 instead of 60 | DP |
< instead of <= for compatibility | back-to-back jobs counted as clashing | end ≤ next start is compatible |
| A linear scan for the last compatible job | O(n²) | binary search on sorted ends |
int totals | 100,000 big payouts wrap | long |
| Running the one-worker DP twice for two workers | 93 instead of 97 | a real two-worker method |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why sort by end time for the take-or-skip recurrence?
Show answer
Then every job compatible with job i (ending by its start) comes before it, in one contiguous prefix of the list. best[k] for that prefix is already computed, and binary search over the sorted end times finds k in O(log n).
2. Jobs (1-2, 10), (2-3, 10), (1-3, 100). What does "earliest end first" give, and what's optimal?
Show answer
Greedy takes 1-2 and 2-3 for 20; the single job 1-3 is worth 100. Earliest-end greedy maximizes the number of jobs, not their total profit.
3. A job ends at 5 and another starts at 5. Compatible?
Show answer
Yes - with half-open intervals [start, end), the first is over when the second begins. The binary search must count jobs with end <= start; using < would wrongly exclude back-to-back jobs.
Key takeaways
- Weighted interval scheduling is take-or-skip DP over jobs sorted by end time.
- Compatible earlier jobs form a prefix; binary-search it with end <= start.
- Greedy rules (earliest end, highest profit) fail when jobs have different profits.
- With few integer positions, a right-to-left DP over positions needs no sort at all.
- O(n log n); watch for totals that exceed an int.