DSA problem
Maximum Profit in Job Scheduling
You are given n jobs, where job i has start time startTime[i], end time endTime[i], and profit profit[i]. You may pick any subset of non-overlapping jobs (a job ending at time x is compatible with a job starting at time x). Return the maximum total profit you can earn.
This is the weighted interval scheduling problem. A greedy approach (sort by end time and always take the next compatible job) does not work because greedy ignores profit — a single high-profit job may outweigh many low-profit ones. We need a DP that, for each job, compares "skip it" against "take it plus the best result through the latest compatible earlier job."
Let dp[i] be the maximum profit using only jobs [0..i] after sorting all jobs by end time. The recurrence is dp[i] = max(dp[i - 1], dp[p(i)] + profit[i]), where p(i) is the largest index j < i whose endTime[j] <= startTime[i] (or -1 if no such job). Computing p(i) is a classic binary-search problem because the end times are sorted: search for the rightmost end time that does not exceed startTime[i].
The optimal algorithm sorts the jobs by end time in O(n log n), then for each job performs a binary search to find p(i) and updates the rolling DP. Total time is O(n log n) and total space is O(n).
Examples
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]120startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]150startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]6Constraints
- 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
- 1 <= startTime[i] < endTime[i] <= 10^9
- 1 <= profit[i] <= 10^4
- Jobs ending at time t are compatible with jobs starting at time t.
- You may select any subset of pairwise non-overlapping jobs.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.