Maximum Profit in Job Scheduling
Jobs have start, end, profit. Pick non-overlapping jobs maximizing total profit (touching endpoints allowed).
Intuition
Sort jobs by end time and ask, per job: take it or skip it? Skipping inherits the best so far. Taking it earns its profit plus the best achievable among jobs that finish by its start — and because ends are sorted, that predecessor is found by binary search. Weighted intervals break plain greedy; this DP + bisect handles the weights.
Weighted interval scheduling. Unlike the unweighted version, greedy by end time fails — a single high-paying job can beat several cheap ones — so it becomes DP. Sort by end time, and for each job binary search for the last job that finishes before it starts. Sorting to make a binary search possible is the move.
Approach
Sort by end time
dp is built in end-time order: dp[i] = best profit using the first i jobs. dp[0] = 0.
Take or skip
dp[i+1] = max(dp[i] / skip /, profit_i + dp[k] / take /), where k = number of jobs ending ≤ start_i — found with bisect_right on the sorted end array.
Why greedy fails here
Unweighted interval scheduling is greedy-solvable, but one fat job can beat many thin ones (or vice versa) — profits force trying both branches, which the DP does in O(log n) per job.
Solution & live demo
Common pitfalls
Greedily taking jobs that end earliest
for e, s, p in sorted(zip(endTime, startTime, profit)):
if s >= last_end: total += p; last_end = edp[i + 1] = max(dp[i], dp[k] + p)
That maximises the count of jobs, not the profit. One job worth 100 beats three worth 1 each, and the greedy has no way to see that — the value has to enter the recurrence.
Searching the whole array rather than the prefix
k = bisect_right(ends, s)
k = bisect_right(ends, s, 0, i)
Without the i bound the search can return a job at or beyond the current one, letting a job depend on itself or on a later job. Only jobs already processed are valid predecessors.
Using bisect_left for the predecessor
k = bisect_left(ends, s, 0, i)
k = bisect_right(ends, s, 0, i)
A job ending exactly when this one starts is compatible — no overlap. bisect_left excludes it and needlessly discards a valid chain.
Edge cases
end ≤ start counts as compatible — bisect_right includes it.
dp keeps the single most profitable one.
dp = [0, profit].