Maximum Profit in Job Scheduling – Performance Issue

Posted on

Problem

I implemented the Maximum Profit in Job Scheduling algorithm in JavaScript, but I’m having performance issue.

The problem:
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

My solution:

var jobScheduling = function(startTime, endTime, profit) {
    let possibleStarts = [];
    let startProfit = [];
    let curEnd = Infinity
    let mapPositions = new Map();
    
    for(let i=0; i<startTime.length; i++) {
        const s = startTime[i];
        const e = endTime[i];
        if(s < curEnd) {
            possibleStarts.push([s, e]);
            startProfit.push(i);
            curEnd = Math.min(curEnd, e);
        }
        const temp = mapPositions.get(s) || [];
        temp.push(i);
        mapPositions.set(s, temp);
    }
    
    let output = -Infinity;
    const helper = (queue, count, profitPos) => { 
        const start = queue.shift();
        const end = queue.shift();
        count += profit[profitPos];
        
        // get all possible next start
        for(const [key, value] of mapPositions) {
            if(key >= end) {
                for(const v of value) {
                    helper([startTime[v], endTime[v]], count, v)
                }
            }
        }
        
        output = Math.max(output, count);
        return;
    }
    
    for(let i=0; i<possibleStarts.length; i++) {
        helper(possibleStarts[i], 0, startProfit[i]);
    }
    
    return output;
};

It works for both examples and other test cases. However it fails for the test case below due to time limit.

startTime  = [341,22,175,424,574,687,952,439,51,562,962,890,250,47,945,914,835,937,419,343,125,809,807,959,403,861,296,39,802,562,811,991,209,375,78,685,592,409,369,478,417,162,938,298,618,745,888,463,213,351,406,840,779,299,90,846,58,235,725,676,239,256,996,362,819,622,449,880,951,314,425,127,299,326,576,743,740,604,151,391,925,605,770,253,670,507,306,294,519,184,848,586,593,909,163,129,685,481,258,764]

endTime = [462,101,820,999,900,692,991,512,655,578,996,979,425,893,975,960,930,991,987,524,208,901,841,961,878,882,412,795,937,807,957,994,963,716,608,774,681,637,635,660,750,632,948,771,943,801,985,476,532,535,929,943,837,565,375,854,174,698,820,710,566,464,997,551,884,844,830,916,970,965,585,631,785,632,892,954,803,764,283,477,970,616,794,911,771,797,776,686,895,721,917,920,975,984,996,471,770,656,977,922]

profit = [85,95,14,72,17,3,86,65,50,50,42,75,40,87,35,78,47,74,92,10,100,29,55,57,51,34,10,96,14,71,63,99,8,37,16,71,10,71,83,88,68,79,27,87,3,58,56,43,89,31,16,9,49,84,62,30,35,7,27,34,24,33,100,25,90,79,58,21,31,30,61,46,36,45,85,62,91,54,28,63,50,69,48,36,77,39,19,97,20,39,48,72,37,67,72,46,54,37,53,30]

Solution

There are some readability concerns to me:

  • startTime, endTime, profit are all arrays. The names should be plural to make this obvious.
  • possibleStarts consists of both start and end. It’s confusing. You could instead make an array of job objects with properties start, end, profit. Then you wouldn’t need the extra profit lookup either.
  • helper is not a good function name. It indicates that it’s not entirely clear what you want it to do.
  • count is not a count. It is the profit
  • profitPos is really the job index

Clearing these up will make it easier to understand the current solution, and therefore easier to figure out the performance as well.

About performance:

I think the key to this problem is to realize that helper will be called on the same jobs over and over again. We can exploit this by using memoization. What you need to do is to have the function return a value. If the function is given the same input we’ll just return the previously calculated value instead of running them all again.

You can add memoization like this:

const memo = new Map()
const helper = (queue, count, profitPos) => {
    if (memo.has(profitPos)) return memo.get(profitPos)
    const start = queue.shift();
    const end = queue.shift();

    let maxProfit = 0
    // get all possible next start
    for(const [key, value] of mapPositions) {
        if(key >= end) {
            for(const v of value) {
                const profit = helper([startTime[v], endTime[v]], count, v)
                maxProfit = Math.max(profit, maxProfit)
            }
        }
    }

    const result = profit[profitPos] + maxProfit
    memo.set(profitPos, result)
    return result
}

which can be rewritten into this (glossing over the details):

const memo = new Map()
const getMaxProfit = (index) => {
    if (memo.has(index)) return memo.get(index)
    const job = jobs[index]

    let maxSubProfit = 0
    for (let i = 0; i < jobLen; i++) {
        if (jobs[i].start < job.end) continue
        const profit = getMaxProfit(i)
        maxSubProfit = Math.max(profit, maxSubProfit)
    }

    const maxProfit = job.profit + maxSubProfit
    memo.set(index, maxProfit)
    return maxProfit
}

And this will solve your test case fast enough.

Since we’re memoizing on the job index (profit pos), the function body will only run once for each job. In the function body we still iterate over all jobs (mapPositions). In other words, getMaxProfit is called about n times for every time the loop runs. This is a problem even with memoization since the memo map has to be called n times. The time complexity becomes O(n^2). With n=100 it works fine, but for larger inputs it gets slow again.

There are some pretty clever tricks to avoid the loop involving rewriting the loop as a recursion and adding binary search. The thing to realize is that we’re calling getMaxProfit more than we need to. We always “keep” the profit of the current job, and try out all the upcoming jobs. When we get to the next job, we try all jobs again, calling getMaxProfit each time. And even though it’s fast, it adds up. We can solve it by realizing that we only need to check the next job:

When considering a job, we can either skip the job and move on, or we can keep the job and find the next job after the current one. The reason we can just consider the next job (as opposed to ALL the possible next jobs as in the loop) is that the first option of skipping a job ensures that we explore all solutions anyway, including actually skipping the next job we found.

So with this we have managed to remove the loop that calls getMaxProfit. But we have a new loop that’s supposed to find the next job, and this loop is itself a problem. But it’s much easier to solve, for example using binary search.

The code might look something like this:

const jobs = startTimes
    .map((start, i) => ({ start, end: endTimes[i], profit: profits[i] }))
    .sort((a, b) => a.start > b.start ? 1 : -1)

const memo = new Map()
const getMaxProfit = (index) => {
    if (index >= jobs.length) return 0
    if (memo.has(index)) return memo.get(index)

    const job = jobs[index]

    const nextIndex = findNextJobIndex(jobs, job.end)
    const maxProfitNext = getMaxProfit(nextIndex)
    const maxProfitSkipped = getMaxProfit(index + 1)

    const maxProfit = Math.max(maxProfitNext + job.profit, maxProfitSkipped)

    memo.set(index, maxProfit)
    return maxProfit
}

return getMaxProfit(0)

Leave a Reply

Your email address will not be published. Required fields are marked *