Maximum Profit in Job Scheduling
MediumSort by end, binary search the last compatible job
Problem
Given jobs with start, end and profit, maximize total profit with no overlapping jobs.
Sort by start; for each job choose skip, or take it plus the best job that starts after it ends.
The idea
Sort the jobs by end time so that when considering a job you can binary search for the latest one finishing at or before its start. The best answer is then the maximum of skipping the job or taking it plus that earlier best.
The trick
- Sort by end time, then binary search within the processed prefix.
- Keep the running best monotonic so the search result is usable directly.
- O(n log n).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — startTime, endTime, profit Values: 0.
1sort by end time2dp[i]=max(dp[i-1], profit[i]+dp[latest job ending <= start[i]])Input
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- start=[1,2,3,3], end=[3,4,5,6], profit=[50,10,40,70]
- Output:
- 120
- Explanation:
- Take jobs 1 and 4 → 120.
Example 2
- Input:
- start=[1,2,3,4,6], end=[3,5,10,6,9], profit=[20,20,100,70,60]
- Output:
- 150
- Explanation:
- Best non-overlapping set → 150.
Example 3
- Input:
- start=[1,1,1], end=[2,3,4], profit=[5,6,4]
- Output:
- 6
- Explanation:
- They all overlap → take the best, 6.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.