Problem
Each job has a start time, end time and profit. Choose compatible jobs to maximise total profit. A job may start exactly when another ends.
Worked examples
Input: jobs = [(1,3,20),(2,5,50),(3,6,40)]
Output: 60
Choose the first and third jobs; 20 + 40 exceeds 50.
Hints
Hint 1
Sort jobs by finishing time.
Hint 2
For each job, locate the last compatible earlier job.
Solution approach
- Sort jobs by end time. Let dp[i] be the best profit using the first i jobs.
- For job i, binary-search its last compatible predecessor. Compare skipping the job with taking it plus that predecessor profit.
- Record choices if the selected schedule is also needed.
Complexity
O(n log n) time and O(n) space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗