[LeetCode] 826. Most Profit Assigning Work (JS)

[LeetCode] 826. Most Profit Assigning Work (JS)

題目

題目會提供三個陣列: difficultyprofitworker 其中:

  • difficulty:工作的難度
  • profit:工作的利潤
  • worker:工人的能力(工人最多能完成的難度)

每個工人最多只能分配一項工作,但一項工作可以給多個工人做。

請計算出分工後能獲得的最大利潤。

Example 1

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

Example 2

Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0

Constraints:

  • n == difficulty.length
  • n == profit.length
  • m == worker.length
  • 1 <= n, m <= 104
  • 1 <= difficulty[i], profit[i], worker[i] <= 105

解題思路

  1. 首先需要將工作按照難度進行排序,並且在排序後保留對應的利潤
  2. 在遍歷工人的時候需要跟蹤能完成的工作的最大利潤,以便快速查找
  3. 遍歷每個工人,找出他們能完成的最難的工作,並將該工作的利潤累加到總利潤中

題目給的範例已經按照大小排序過所以不好演示,我用下面的例子說明:

difficulty: [10,5,7,13,20]
profit: [15,10,20,30,5]
worker: [8,2,3,7]

1.首先將 difficultyprofit 結合成一個二維陣列,然後按照 difficulty 進行排序:

const jobs = difficulty.map((diff, i) => [diff, profit[i]]).sort((a, b) => a[0] - b[0])
// jobs = [[10, 15], [5, 10], [7, 20], [13, 30], [20, 5]]
// 難度由小至大排序 => [[5, 10], [7, 20], [10, 15], [13, 30], [20, 5]]

2.接著要計算每個工作之前的最大利潤:

  • 創建一個陣列 maxProfitAtDifficulty,用於記錄每個難度能夠獲得的最大利潤
  • 遍歷排序後的 jobs,更新 maxProfitAtDifficulty,確保每個難度級別的利潤是該難度及之前所有工作的最大利潤
let maxProfitAtDifficulty = [] // 難度對應的最大利潤
let maxProfit = 0 // 當前最大的利潤

for (let i = 0; i < jobs.length; i++) {
  maxProfit = Math.max(maxProfit, jobs[i][1])
  maxProfitAtDifficulty.push([jobs[i][0], maxProfit])
}
// jobs = [[5, 10], [7, 20], [10, 15], [13, 30], [20, 5]]
// maxProfit = 10, 20, 20, 30, 30
// maxProfitAtDifficulty = [[5, 10], [7, 20], [10, 20], [13, 30], [20, 30]]

3.最後計算總利潤:

  • 遍歷每個工人,對於每個工人找到他們能完成的最大難度工作對應的利潤,並累加到總利潤中
  • 可以用二元搜索法來找對應的最大利潤
  • 例如,對於 worker = [8,2,3,7],通過二元搜索法,可以找到對應的最大利潤分別是 20, 0, 0, 20,最終總利潤為 40
let totalProfit = 0 // 每個員工的最大利潤總和
// 找到 worker 能完成的最大難度工作, worker = [8,2,3,7]
for (let w of worker) {
  // 雙指針(索引) left: 0, right: 4
  let left = 0, right = maxProfitAtDifficulty.length - 1
  // 二元搜索法
  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    // // maxProfitAtDifficulty = [[5, 10], [7, 20], [10, 20], [13, 30], [20, 30]]
    if (maxProfitAtDifficulty[mid][0] <= w) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  // 加入對應的最大利潤
  if (right >= 0) {
    // worker = [8,2,3,7]
    // (1) totalProfit += 20
    // (2) right < 0 所以跳過
    // (3) right < 0 所以跳過
    // (4) totalProfit += 20
    totalProfit += maxProfitAtDifficulty[right][1]
  }
}

完整程式碼

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
    const jobs = difficulty.map((diff, i) => [diff, profit[i]]).sort((a, b) => a[0] - b[0])

    let maxProfitAtDifficulty = []
    let maxProfit = 0

    for (let i = 0; i < jobs.length; i++) {
      maxProfit = Math.max(maxProfit, jobs[i][1])
      maxProfitAtDifficulty.push([jobs[i][0], maxProfit])
    }
    
    let totalProfit = 0;
    for (let w of worker) {
      let left = 0, right = maxProfitAtDifficulty.length - 1
      while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        if (maxProfitAtDifficulty[mid][0] <= w) {
          left = mid + 1
        } else {
          right = mid - 1
        }
      }

      if (right >= 0) {
        totalProfit += maxProfitAtDifficulty[right][1]
      }
    }
    return totalProfit
};
image 4
guest

0 評論
內聯回饋
查看全部評論