Find Maximum Profit in Job Scheduling in JavaScript

I recently came across an interview question posted on Geeks For Geeks! Even though questions might not be the same, the first rounds are usually coding tests, and it's always good to have some practice done on such dynamic programming questions.

Given three arrays called pickup, drop, and tip. Find the max profit the delivery guy can earn. The guy can only process one delivery at a time.

Example: He gets profit of 5 - 0 + 1 = 6
6 units if the 1st order is delivered
pickup: [0,2,9,10,11,12]
drop:[5,9,11,11,14,17]
tip:[1,2,3,2,2,1]

This program looks like a variation of ‘Maximum Profit in Job Scheduling’ :

We have three arrays, start, end, profit for N jobs. Then, the program should return the maximum profit when no two jobs overlap the same time range, i.e., every scheduled job is to be done from start[i] to end[i] with a profit of profit[i].

Example:
Input: start = [2, 3, 4, 6, 7], end = [4,6,11,7,10] and profit =[30,30,200,80,70]
Output: 180
How?: The elements chosen are the first, fourth, and fifth jobs.
Thus, we will get the profit of 180 = 30 + 80 + 70.

Implementation using JavaScript:

First, we create an array of objects using the given start, end, profit arrays. Example:

const myJobObject = [{
  start: 2,
  end: 4,
  profit: 30
}]

For this, we’ll create a method that accepts the start, end, and profit arrays. Loop over them and store all the myJobObjects in an array as shown below:

const jobScheduling = (start, end, profit) => {
   const myJobObject = [];
   for (let i = 0;  i<start.length;  i++) {
      myJobObject.push({
          start: start[i],
          end: end[i],
          profit: profit[i]
      });
   } 
  
}

This is a Greedy Algorithm problem, and in any greedy problem, we follow a problem-solving technique to solve the problem at each step of the solution optimally. Therefore, We want to build a solution that will give us an optimal solution with an immediate effect!

Maximum Profit in Job Scheduling is the same as Weighted Interval Scheduling where we need to schedule non-overlapping tasks of maximum weight in a given time frame.
As per the analysis of Weighted Interval Scheduling, we will sort the array by end time in ascending order, i.e., Earliest Finish Time.

Thus, now we’ll sort our myJobObject by end time and add a sorting comparator to our piece of code:

function sortObj(obj1, obj2) {
    return (obj1.end - obj2.end);
}
const jobScheduling = (start, end, profit) => {
   const myJobObject = [];
   for (let i = 0;  i<start.length;  i++) {
      myJobObject.push({
          start: start[i],
          end: end[i],
          profit: profit[i]
      });
   } 
    //sort as per endtime
    myJobObject.sort(sortObj);
}

We now need to identify the latest non-conflict delivery (i.e., finding the latest job which does not conflict with our current job). For this we’ll do a simple linear search on our object array and return the index of the next non-conflicting job:

function findLatestNonConflictDelivery(myJobObject, i) {
    for (let j=i-1; j>=0; j--) {
        if (myJobObject[j].end <= myJobObject[i].start)
            return j;
    }
    return -1;
}

We will now put the pieces together and find the maximum profit:

function findMaxProfit(myJobObject){
    
    let n = myJobObject.length;
    
    let maxProfit = [];
    
    //initializing first profit
    maxProfit[0] = myJobObject[0].profit; 
    
    for (let i=1; i<n; i++) {
        let j = findLatestNonConflictDelivery(myJobObject, i);
        let profit = myJobObject[i].profit;
        
        if (j != -1) {
           //when next non conflicting job is found
           profit = maxProfit[j] + profit;
        }
 
        //we will store max
        maxProfit[i] = Math.max(profit, maxProfit[i-1]);
    }
 
    //we will store the result of the max profit
    let result = maxProfit[n-1];
 
    return result;
}

That’s all.
Now practice this problem on the leetcode platform here!

Reference to other programming questions —
Convery Binary Number in a Linked List to Integer
Find Perfect, Deficient, and Abundant Numbers
Find how many Sundays fell on the first of the month for the given year