333. Maximum Profit in Job Scheduling

Sort jobs by end time. For each job, the best profit is either skipping it, or taking it plus the best profit among jobs that finish by its start — found with binary search.

DP over end-sorted jobs

Sort jobs by end time. Let dp[i] = max profit using the first i jobs. For job i, either skip it (dp[i-1]) or take it: its profit plus dp[idx], where idx is the number of earlier jobs whose end ≤ this job's start (a binary search on the sorted end times).

dp[i] = max(dp[i-1], profit_i + dp[bisect_right(ends, start_i)])

Worked example

start [1,2,3,3], end [3,4,5,6], profit [50,10,40,70] → take jobs 1 and 4 for 120.

Complexity

• Time: O(n log n).
• Space: O(n).

import java.util.Arrays;

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];  // {end, start, profit}
        for (int i = 0; i < n; i++) {
            jobs[i][0] = endTime[i];
            jobs[i][1] = startTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        int[] endSorted = new int[n];
        for (int i = 0; i < n; i++) endSorted[i] = jobs[i][0];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int st = jobs[i - 1][1], pr = jobs[i - 1][2];
            int idx = upperBound(endSorted, st, i - 1);
            dp[i] = Math.max(dp[i - 1], dp[idx] + pr);
        }
        return dp[n];
    }

    private int upperBound(int[] a, int key, int hi) {
        int lo = 0;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (a[mid] <= key) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}