Leetcode 1235. Maximum Profit in Job Scheduling

Clarification

Okay, first I'll restate the problem to make sure I understand it correctly.

We are given three arrays:

• startTime[i]: when job i starts
• endTime[i]: when job i finishes
• profit[i]: the profit we get from doing job i

We need to select a set of non-overlapping jobs that gives us the maximum total profit.

Can two jobs overlap if one starts exactly when another finishes?
Can jobs have the same start or end time?
Do I need to return the maximum profit only, not the selected jobs?

Assuming yes, this is starting to look like a 0/1 knapsack problem with constraints.

Brute-force Approach

The simplest approach would be to consider every possible subset of jobs.

For each job, I have two choices:

• Take this job.
• Skip this job.

So I can recursively explore all possible combinations. However, there are n jobs, and each job has two choices O(2^n), which is too slow.

Optimization

This is essentially 0/1 knapsack, instead of constraint on the item weight, this problem constraints on the job start and end time.

First I need to sort the jobs by start time and end time, because for each job, I need to know the next job that starts after this job finishes.

Then I can define dp[i] as the maximum profit we can get considering jobs from index i onwards.

For each job i, I have two choices.

• Skip this job: dp[i + 1]
• Take this job: profit[i] + dp[nextIndex]

So the transition is:

dp[i] = max(
    dp[i+1],
    profit[i] + dp[nextIndex]
)

Another important part is, after taking job i of endTime[i], I need to find the first job where startTime >= endTime[i].

Because jobs are sorted by start time, I can use binary search. Without binary search, the time cost would be O(n) for every job. With binary search, it would be O(log n).

Sorting costs O(nlogn). There are n jobs and for each job the dp function costs O(logn) because of the binary search, so overall O(nlogn). Therefore time complexity would be O(nlogn).

Space is O(n) because of: memo array, jobs array, and recursion stack.

Code

class Solution {

    record Job(
            int startTime,
            int endTime,
            int profit
    ) {}


    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // 0-1 knapsack
        List<Job> jobs = getJobs(startTime, endTime, profit);
        Integer[] memo = new Integer[startTime.length + 1];

        return dp(jobs, 0, memo);
    }

    private int dp(List<Job> jobs, int available, Integer[] memo) {
        if (available == jobs.size()) {
            return 0;
        }
        if (memo[available] != null) {
            return memo[available];
        }

        // not take current job
        int result = dp(jobs, available + 1, memo);
        // take current job
        Job curr = jobs.get(available);
        // binary search next available job
        int next = binarySearch(jobs, available + 1, curr.endTime);
        result = Math.max(dp(jobs, next, memo) + curr.profit, result);
        memo[available] = result;

        return result;
    }

    // [left, right]
    // find first element which value is greater than or equal to key
    // if no, return list size
    private int binarySearch(List<Job> jobs, int leftBound, int key) {
        if (leftBound == jobs.size() || jobs.getLast().startTime < key) {
            return jobs.size();
        }

        int left = leftBound, right = jobs.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (jobs.get(mid).startTime < key) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }

        return left;
    }

    private List<Job> getJobs(int[] startTime, int[] endTime, int[] profit) {
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < startTime.length; i++) {
            jobs.add(new Job(startTime[i], endTime[i], profit[i]));
        }
        Collections.sort(jobs, (a, b) -> a.startTime != b.startTime ?
                Integer.compare(a.startTime, b.startTime) :
                Integer.compare(a.endTime, b.endTime));

        return jobs;
    }
}

Follow-up

Can you make it iterative?

Yes. We can replace DFS with bottom-up DP.

Instead of dp[i] from index i onward, we can process jobs from right to left:

dp[i] = max(
    dp[i+1],
    profit[i] + dp[next]
)

The binary search part stays the same.