610. Maximum Profit in Job Scheduling
There are n jobs on offer. Job i occupies the time window from startTime[i] to endTime[i] and pays profit[i] on completion. You can hold only one job at any moment, but back-to-back is fine: a job ending at time t does not clash with another that starts exactly at t.
Given the three arrays startTime, endTime, and profit, choose a set of pairwise non-overlapping jobs whose combined pay is as large as possible, and return that maximum total profit as an integer.
Example 1:
Input: startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70]
Output: 120
Explanation: Take job 1 (time 1→3, pays 50) and job 4 (time 3→6, pays 70). Job 1 ends exactly when job 4 begins, which is allowed. Total: 120.
Example 2:
Input: startTime = [1, 2, 3, 4, 6], endTime = [3, 5, 10, 6, 9], profit = [20, 20, 100, 70, 60]
Output: 150
Explanation: Take job 1 (1→3, pays 20), job 4 (4→6, pays 70), and job 5 (6→9, pays 60) for 150. The 100-profit job blocks the whole middle of the timeline, so it is not worth it here.
Constraints:
- 1 ≤ n ≤ 5 * 10⁴
- 1 ≤ startTime[i] < endTime[i] ≤ 10⁹
- 1 ≤ profit[i] ≤ 10⁴
Hints:
Greedy by profit or by earliest end fails once pay is uneven — a cheap job can block a lucrative one. Sort the jobs by end time and make one clean decision per job: skip it, or take it.
Let best[i] be the top profit using only the first i jobs in end order. Taking job i earns profit_i plus best[j], where j is the count of jobs finishing by start_i. Since the end times are sorted, find j with a binary search: best[i] = max(best[i−1], profit_i + best[j]).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70]
Expected output: 120