Description
Given n jobs with start time, end time and profit, find the maximum profit subset of non-overlapping jobs. Use DP with binary search.
Examples
Input:
startTime=[1,2,3,3], endTime=[3,4,5,6], profit=[50,10,40,70]Output:
120Explanation:
Jobs 1 and 4 give 50+70=120.
Input:
startTime=[1], endTime=[1], profit=[1]Output:
1Explanation:
Edge case with a single-element array.
Input:
startTime=[1,2,4,6,8], endTime=[3,5,7,9,10], profit=[20,30,40,10,50]Output:
120Explanation:
Selecting non-overlapping jobs for maximum profit: jobs 1 and 3 (times [1,3] and [4,7]) give 20+40=60, jobs 2 and 5 (times [2,5] and [8,10]) give 30+50=80. The optimal selection yields the maximum profit of 110.
Constraints
- •
1 ≤ n ≤ 5 * 10⁴ - •
1 ≤ startTime[i] < endTime[i] ≤ 10⁹