Schedule non-overlapping jobs to maximize total profit.
Input: startTime=[1,2,3,3], endTime=[3,4,5,6], profit=[50,10,40,70] → Output: 120
Input: startTime=[1,2,3,4,6], endTime=[3,5,10,6,9], profit=[20,20,100,70,60] → Output: 150
Sort jobs by end time. DP with binary search to find last non-conflicting job.
- Sort jobs by end time
- dp[i] = max profit using first i jobs
- For each job i: binary search for last job ending <= start[i]
- dp[i] = max(dp[i-1], dp[j]+profit[i])
- Return dp[n]
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
int[][] jobs = new int[n][3];
for (int i = 0; i < n; i++) jobs[i] = new int[]{endTime[i], startTime[i], profit[i]};
Arrays.sort(jobs, (a,b) -> a[0] - b[0]);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int start = jobs[i-1][1];
int lo = 0, hi = i - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (jobs[mid-1][0] <= start) lo = mid;
else hi = mid - 1;
}
dp[i] = Math.max(dp[i-1], dp[lo] + jobs[i-1][2]);
}
return dp[n];
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)