Maximum Profit in Job Scheduling

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, you need to output the maximum profit you can take such that there are no 2 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

 

Constraints:

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

Solution(javascript)

/*
 * @lc app=leetcode id=1235 lang=javascript
 *
 * [1235] Maximum Profit in Job Scheduling
 */

// @lc code=start
/** MIT Weighted Interval Scheduling
 * http://www.cs.umd.edu/class/fall2017/cmsc451-0101/Lects/lect10-dp-intv-sched.pdf
 * Top-down approach: stack overflow
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
// const jobScheduling = function (startTime, endTime, profit) {
//   const arr = startTime.reduce((acc, start, index) => {
//     acc.push([start, endTime[index], profit[index]])
//     return acc
//   }, [])
//   arr.sort((a, b) => a[1] - b[1])
//   const memo = []
//   let max = 0
//   const aux = (index) => {
//     if (index < 0) {
//       return 0
//     }
//     if (memo[index] !== undefined) {
//       return memo[index]
//     }
//     let prevIndex = -1
//     for (let i = index - 1; i >= 0; i--) {
//       if (arr[i][1] <= arr[index][0]) {
//         prevIndex = i
//         break
//       }
//     }
//     memo[index] = Math.max(
//       aux(index - 1),
//       arr[index][2] + aux(prevIndex),
//     )
//     max = Math.max(max, memo[index])
//     return memo[index]
//   }
//   aux(arr.length - 1)
//   return max
// }

const jobScheduling = function (startTime, endTime, profit) {
  const arr = startTime.reduce((acc, start, index) => {
    acc.push([start, endTime[index], profit[index]])
    return acc
  }, [])
  arr.sort((a, b) => a[1] - b[1])
  const memo = []
  let max = 0
  const getPrevIndex = (left, right, target) => {
    let result = -1
    while (left <= right) {
      const middle = Math.floor((left + right) / 2)
      if (arr[middle][1] <= target) {
        left = middle + 1
        result = middle
      } else {
        right = middle - 1
      }
    }
    return result
  }
  for (let i = 0; i < arr.length; i++) {
    const prevIndex = getPrevIndex(0, i, arr[i][0])
    memo[i] = Math.max(
      (memo[i - 1] || 0),
      arr[i][2] + (memo[prevIndex] || 0),
    )
    max = Math.max(max, memo[i])
  }
  return max
}