Maximum Profit in Job Scheduling

Loading...LeetCode

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.

Example 3:

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

Pseudocode

- initial attemp to solve via graph 
    - one tasks are connected to others
- optimal solution is combination of dfs and binary search

Solution

// from solution
// top down DP with memo
// https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/733167/thinking-process-top-down-dp-bottom-up-dp/
var jobScheduling = function (startTime, endTime, profit) {
  const jobs = new Array(startTime.length);
  const dp = new Map();

  // make a new array containing start, time and profit
  for (let i = 0; i < jobs.length; i++) {
    jobs[i] = [startTime[i], endTime[i], profit[i]];
  }

  // sort according to start time
  jobs.sort((a, b) => a[0] - b[0]);

  return dfs(0, jobs, dp);
};

function dfs(idx, jobs, dp) {
  // base condition
  if (idx === jobs.length) {
    return 0;
  }

  if (dp.has(idx)) {
    return dp.get(idx);
  }

  // pre
  // given this particular job idx, find the next idx that has a non-overlapping start time
  let next = binarySearch(idx, jobs);

  // recurse
  let inclProfit = jobs[idx][2] + (next === -1 ? 0 : dfs(next, jobs, dp));
  let exclProfit = dfs(idx + 1, jobs, dp);

  // post
  dp.set(idx, Math.max(inclProfit, exclProfit));
  return Math.max(inclProfit, exclProfit);
}

function binarySearch(idx, jobs) {
  let lo = idx + 1;
  let hi = jobs.length - 1;

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

    // returns the next job by comparing, mid start time to idx end time
    if (jobs[mid][0] >= jobs[idx][1]) {
      // if start time of prev is also equals or more than idx end time, continue seraching
      if (jobs[mid - 1][0] >= jobs[idx][1]) {
        hi = mid - 1;

        // if prev job start time is less than idx end time, return
      } else {
        return mid;
      }
    } else {
      lo = mid + 1;
    }
  }
  return -1;
}

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -