Hard · Sort and Predecessor DP
Understand → Visualise → Practice.
Each job is `[start,end,profit]`. Select non-overlapping half-open jobs with maximum total profit.
With jobs sorted by end time, the best profit using the first i jobs is either the best without job i, or job i's profit plus the best among jobs ending by its start (found by binary search).
Order jobs by end time and keep the list of end times.
For job i, binary search for how many earlier jobs end at or before its start.
dp[i + 1] = max(dp[i], profit_i + dp[compatible]); the last entry is the answer.
O(n log n) time and O(n) space.
Picking the most profitable job first (greedy) fails; e.g. one big job can block two jobs that together pay more.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.