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

內容目錄 隱藏

題目

題目會提供三個陣列： difficulty 、 profit 和 worker 其中：

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 <= 10⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵

解題思路

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

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

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

1.首先將 difficulty 和 profit 結合成一個二維陣列，然後按照 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
};

瀏覽量: 21