1235. Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling

Problem Description

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 ranges.

If you choose a job that ends at the time X you will be able to start another job that starts at the 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.

Example 3:

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

 

Constraints:

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
• 1 <= startTime[i] < endTime[i] <= 109
• 1 <= profit[i] <= 104

Approach) Binary Search

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
var jobScheduling = function(startTime, endTime, profit) {
    /*
    Approach: 
    We can have a single array jobs with all the information start,end and profit.
    Then sort this array by start time.
    Now, we can use simple backtracking with memoization.
    In each step we can either take the current job or leave it.
    We if take the current job then the next possible index will be the index of the job which is starting after endTime of the current job.  To find the next possible index, we can use binary search. 
    */
    let jobs=[],cache=[];
    for(let i=0;i<startTime.length;i++){
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort(function(a,b){return a[0]-b[0]});
    return backtrack(0);
    function backtrack(pos){
        if(cache[pos]!==undefined){
            return cache[pos];
        }
        if(pos===startTime.length || pos==-1){
            return 0;
        }
        let profit1=0,profit2=0;
        let nextPossibleJobIndex = binarySearch(jobs[pos][1],pos+1,startTime.length-1);
            profit1 = +jobs[pos][2]+backtrack(nextPossibleJobIndex);//Take this job
        
        profit2 = backtrack(pos+1);//Don't  take this job
        let res = Math.max(profit1,profit2);
        cache[pos] = res;
        return cache[pos];
    }
    
    function binarySearch(key,left,right){
        let mid,ans=-1;
        while(left<=right){
              mid = Math.floor(left + (right-left)/2);
            if(jobs[mid][0]>=key){
                ans = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return ans;
    }
};

Approach) DFS + Memo

var jobScheduling = function(startTime, endTime, profit) {
    let intervals = [];
    for (let i = 0; i < startTime.length; i++) {
        intervals.push({ start: startTime[i], end: endTime[i], profit: profit[i] });
    }
    
    intervals.sort((a,b) => a.start - b.start);
    let memo = new Array(intervals.length + 1);
    return dfs(0);
    
    function dfs(startIdx) {
        if (memo[startIdx] !== undefined) {
            return memo[startIdx];
        }
        
        if (startIdx >= intervals.length) {
            return 0;
        }
        
        // taking
        let idx = startIdx;
        let take = intervals[startIdx];
        while (intervals[idx]?.start < take?.end) {
            idx++;
        }
        
        const takeProfit = take.profit + dfs(idx);
        // not taking
        const notTakeProfit = dfs(startIdx + 1);
        let res = Math.max(takeProfit, notTakeProfit);
        memo[startIdx] = res;
        return res;
    }
};

Approach) Dynamic Programming

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
var jobScheduling = function(startTime, endTime, profit) {
    if (startTime === null || endTime === null || profit === null) {
        return 0;
    }
    
    const lists = startTime.map((time, index) => {
        return [time, endTime[index], profit[index]];
    })
    lists.sort((a, b) => a[1] - b[1]);
    const dp = [];
    dp[0] = lists[0][2];
    for (let i = 1; i < lists.length; i++) {
        const index = findLowestIndex(lists, i);
        if (lists[index][1] <= lists[i][0]) {
            dp[i] = Math.max(dp[i - 1], dp[index] + lists[i][2]);
        } else {
            dp[i] = Math.max(dp[i - 1], lists[i][2]);
        }
    }
    return dp[lists.length - 1];
};

const findLowestIndex = (lists, i) => {
    let l = 0, r = i - 1;
    while (l + 1 < r) {
        let mid = (l + r) >> 1;
        if (lists[mid][1] <= lists[i][0]) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (lists[r][1] <= lists[i][0]) {
        return r;
    } else {
        return l;
    };
}

Approach) Two Pointer + Merge Sort

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

  let zip = [];
  for(let i = 0; i < N; i++) {
    zip.push([startTime[i], endTime[i], profit[i]]);
  }
  const starts = mergesort(zip, (a, b) => a[0] - b[0]).map(s => s[0]);
  const endAsc = mergesort(zip, (a, b) => a[1] - b[1]);
  const ends = endAsc.map(s => s[1]);
  
  const startToClosestEnd = {};
  let j = 0;
  for(const start of starts) {
    let curEnd = ends[j];
    let nextEnd = ends[j+1];
    // While the current and next end are before the current start...
    while(curEnd <= start && nextEnd && nextEnd <= start) {
      // Advance one end.
      j++;
      curEnd = ends[j];
      nextEnd = ends[j+1];
    }
    
    if(curEnd <= start) {
      startToClosestEnd[start] = curEnd;
    } else {
      startToClosestEnd[start] = null;
    }
  }

  let maxProfit = Number.MIN_SAFE_INTEGER;
  
  const bestAtEnd = {};
  for(const [start, end, profit] of endAsc) {
    if(startToClosestEnd[start]) {
      maxProfit = Math.max(maxProfit, bestAtEnd[startToClosestEnd[start]] + profit);
    } else {
      maxProfit = Math.max(maxProfit, profit);
    }
    
    bestAtEnd[end] = maxProfit;
  }

  return maxProfit;
};

function mergesort(arr, comparator) {
  if(arr.length === 1) return arr;

  const mid = Math.floor((arr.length - 1) / 2);
  const a = mergesort(arr.slice(0, mid+1), comparator);
  const b = mergesort(arr.slice(mid+1), comparator);
  const c = [];

  while(a.length || b.length) {
    if(a.length && b.length) {
      if(comparator(a[0], b[0]) < 0) {
        c.push(a.shift());
      } else {
        c.push(b.shift());
      }
    } else if(b.length) {
      c.push(b.shift());
    } else {
      c.push(a.shift());
    }
  }

  return c;
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 1235. Maximum Profit in Job Scheduling

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!