Maximum Profit in Job Scheduling

return maximum profit after job secduling

Maximum Profit in Job Scheduling

Problem

There are n jobs. Job i runs from startTime[i] to endTime[i] and gives profit[i].

Return the maximum profit you can get, so that no two chosen jobs overlap in time.

If a job ends at time X, you can start another job at time X.

Examples

Example 1

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

• Choose job 1 (time 1-3) and job 4 (time 3-6).
• Profit = 50 + 70 = 120.

Example 2

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

• Choose jobs 1, 4 and 5.
• Profit = 20 + 70 + 60 = 150.

Example 3

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

• All jobs start at time 1, so only one job can be chosen.
• The best one gives 6.

Constraints

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

Main Idea

This is a pick or not pick problem, like the stock and LIS problems.

Step 1: Sort the jobs

• Put the three arrays together into one list of [start, end, profit].
• Sort the list by start time.

Step 2: Choices for each job

Let solve(i) be the maximum profit we can get from jobs i to n - 1.

For job i, we have two choices:

• Not pick: Skip this job. The answer is solve(i + 1).
• Pick: Take the profit of this job. Then we jump to the next job that starts at or after the end time of job i. Call its index next. The answer is profit[i] + solve(next).

We take the maximum of both choices.

Step 3: Find the next job with binary search

The jobs are sorted by start time. So the jobs that start at or after end[i] form a block on the right side.

• We need the first index j where start[j] >= end[i].
• We find it with binary search, in O(log n).
• If no such job exists, the answer is n. Then solve(n) returns 0.

Note: We use >=, because a job can start at the same time that another job ends.

Base Case

• If i >= n, there are no jobs left. Return 0.

Helper: Build the Jobs and Find the Next Job

All three solutions use the same setup. First we make the sorted list of jobs. Then we use a binary search to find the next job.

const n = startTime.length;

// combine the three arrays and sort by start time
const jobs = [];
for (let i = 0; i < n; i++) {
    jobs.push([startTime[i], endTime[i], profit[i]]);
}
jobs.sort((a, b) => a[0] - b[0]);

// first index j (after i) where jobs[j] starts at or after jobs[i] ends
function nextJob(i) {
    let lo = i + 1;
    let hi = n;

    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);

        if (jobs[mid][0] >= jobs[i][1]) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo; // equals n when no job is found
}

How nextJob Works

• We search in the range i + 1 to n. Jobs before this range start earlier, so they cannot be next.
• If the middle job starts at or after end of job i, it could be the answer, but an earlier one may also work. So we move hi = mid.
• Otherwise, it starts too early. So we move lo = mid + 1.
• When lo === hi, we found the first valid job.

Solution 1: Plain Recursion

This version tries all choices. It does not save any answer, so it repeats the same work many times.

var jobScheduling = function (startTime, endTime, profit) {
    const n = startTime.length;

    const jobs = [];
    for (let i = 0; i < n; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[0] - b[0]);

    function nextJob(i) {
        let lo = i + 1;
        let hi = n;

        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);

            if (jobs[mid][0] >= jobs[i][1]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

    function solve(i) {
        // no jobs left
        if (i >= n) return 0;

        // skip this job
        const notPick = solve(i + 1);

        // take this job, then jump to the next job that does not overlap
        const pick = jobs[i][2] + solve(nextJob(i));

        return Math.max(pick, notPick);
    }

    return solve(0);
};

Complexity

• Time Complexity: O(2^n)
  • Each job has two choices: pick or not pick.
  • The same solve(i) is called again and again.
• Space Complexity: O(n)
  • There is no table.
  • The recursion stack can go as deep as n.

Note: This version is too slow for n = 5 * 10^4. It is shown only to build the idea.

Solution 2: Memoization (Top-Down)

The only thing that changes in solve(i) is i. So there are only n different states. We save each answer in a dp array. Next time, we read it from the array.

var jobScheduling = function (startTime, endTime, profit) {
    const n = startTime.length;

    const jobs = [];
    for (let i = 0; i < n; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[0] - b[0]);

    function nextJob(i) {
        let lo = i + 1;
        let hi = n;

        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);

            if (jobs[mid][0] >= jobs[i][1]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

    // -1 means "not solved yet"
    const dp = Array(n).fill(-1);

    function solve(i) {
        // no jobs left
        if (i >= n) return 0;

        // answer is already saved
        if (dp[i] !== -1) return dp[i];

        // skip this job
        const notPick = solve(i + 1);

        // take this job, then jump to the next job that does not overlap
        const pick = jobs[i][2] + solve(nextJob(i));

        return (dp[i] = Math.max(pick, notPick));
    }

    return solve(0);
};

Complexity

• Time Complexity: O(n log n)
  • Sorting takes O(n log n).
  • There are n states, and each state is solved once.
  • Each state does one binary search, which takes O(log n).
• Space Complexity: O(n)
  • The jobs list and the dp array each hold n values.
  • The recursion stack can go as deep as n.

Warning: With n up to 5 * 10^4, a deep recursion may cause a "Maximum call stack size exceeded" error in JavaScript. The tabulation solution below avoids this problem.

Solution 3: Tabulation (Bottom-Up)

In this method, we do not use recursion. We start from the last job and move to the first job.

Here, dp[i] means: the maximum profit from jobs i to n - 1.

• dp[n] = 0, because no jobs are left. This is our base case.
• When we reach i, the values dp[i + 1] and dp[next] are already filled. Both indexes are bigger than i.

var jobScheduling = function (startTime, endTime, profit) {
    const n = startTime.length;

    const jobs = [];
    for (let i = 0; i < n; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[0] - b[0]);

    function nextJob(i) {
        let lo = i + 1;
        let hi = n;

        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);

            if (jobs[mid][0] >= jobs[i][1]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

    // dp[n] = 0 is the base case
    const dp = Array(n + 1).fill(0);

    for (let i = n - 1; i >= 0; i--) {
        // skip this job
        const notPick = dp[i + 1];

        // take this job, then jump to the next job that does not overlap
        const pick = jobs[i][2] + dp[nextJob(i)];

        dp[i] = Math.max(pick, notPick);
    }

    return dp[0];
};

How the Code Works

• Step 1: Build the jobs list and sort it by start time.
• Step 2: Create dp with n + 1 cells. All start at 0, so dp[n] = 0 is already set.
• Step 3: Loop from the last job to the first job.
  • notPick = dp[i + 1] is the best profit if we skip job i.
  • pick = profit + dp[nextJob(i)] is the best profit if we take job i.
  • dp[i] is the maximum of both.
• Step 4: Return dp[0]. It is the best profit from all jobs.

Complexity

• Time Complexity: O(n log n)
  • Sorting takes O(n log n).
  • The loop runs n times, and each step does one binary search in O(log n).
• Space Complexity: O(n)
  • The jobs list and the dp array each hold about n values.
  • There is no recursion stack.

Dry Run

Let us take startTime = [1,2,3,3], endTime = [3,4,5,6] and profit = [50,10,40,70].

Sorted jobs (by start time), as [start, end, profit]:

Next job for each index:

Fill the table from the back. We start with dp[4] = 0.

The answer is dp[0] = 120. This matches the expected output.

Comparison

Summary

• This is a pick or not pick dynamic programming problem.
• First, sort the jobs by start time.
• For each job, we have two choices:
  • Not pick: Move to the next job, i + 1.
  • Pick: Add the profit, and jump to the first job that starts at or after this job ends.
• We find that next job with binary search, because the jobs are sorted.
• We use >= for the start time, because a job can start when another job ends.
• Plain recursion is exponential, because it repeats the same i.
• Memoization saves each dp[i], so there are only n states.
• Tabulation fills the table from the back. It has no recursion, so it is the safest for large inputs.
• Memoization and tabulation run in O(n log n) time and use O(n) space.