Maximum Profit in Job Scheduling

Share

Schedule non-overlapping jobs to maximize total profit.

Example 1
Input: startTime=[1,2,3,3], endTime=[3,4,5,6], profit=[50,10,40,70] → Output: 120
Example 2
Input: startTime=[1,2,3,4,6], endTime=[3,5,10,6,9], profit=[20,20,100,70,60] → Output: 150

Solution Approach

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]
Java
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)