826. Most Profit Assigning Work

Leetcode link

解题思路

本题题目有点难懂，而且中间有个小坑，我先来重新描述一下题目的要求：

首先题目规定了总共有 m 份工作与 n 个工人，并且给定了 difficulty，profit，worker 三个数组，其中：

• difficulty 代表工作的难度，限制长度为 m，与 profit 数组一一对应
• profit 代表工作的报酬，限制长度为 m，与 difficulty 数组一一对应
• worker 代表工人的技能水平，限制长度为 n

此外，题目还给了两个限制：

1. 一个工人只能做一次工作，并且做的工作难度不能超过工人自身的技能水平（也就是 worker 数组的对应值）

2. 一个工作可以被多个工人多次完成，并且报酬可以累加

题目要求在这些条件下，计算出所有工人可以获得最高利润的工作分配方法。

在题目中包含的内容只有这么多，但是在实际的测试 case 中，其实还有一个情况是题目忽略的：

1. 相同难度的工作可能有多份，并且其报酬可能不唯一

了解了上述的要求之后，为了使利润最大化，我们需要让每一个工人做能力范围内利润最高的工作，那么我们需要遵循如下步骤：

1. 先使用一个 Map 把所有工作的难度与利润一一对应起来（为了第二步排序之后还能保留对应关系）
2. 给所有的工作难度从小到大排序
3. 根据难度的排序遍历 Map，给所有难度对应的利润调整成：当前难度的工作所能获得的最高利润
4. 遍历所有工人的能力，找出能力范围能获得的最高利润进行加总

Javascript

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
    let result = 0;
    const difficulty2Profit = new Map();
    for(let i=0;i<difficulty.length;i++) {
        // Establish a Difficulty to Profit map
        if (difficulty2Profit.has(difficulty[i])) {
            if (difficulty2Profit.get(difficulty[i]) > profit[i]) continue;
        }
        difficulty2Profit.set(difficulty[i], profit[i]);
    }

    // sort the difficulty in ascending order
    difficulty.sort((a, b)=> a-b);

    // get the maximum profit base on previous difficulty
    for(let i=1;i<difficulty.length;i++) {
        const prevProfit = difficulty2Profit.get(difficulty[i-1]);
        const curProfit = difficulty2Profit.get(difficulty[i]);
        if(prevProfit > curProfit) {
            difficulty2Profit.set(difficulty[i], prevProfit);
        }
    }

    // Calcutale the maximum profit
    for(let i=0;i<worker.length;i++) {
        for(let j=difficulty.length-1;j>=0;j--) {
            if(worker[i] >= difficulty[j]) {
                result += difficulty2Profit.get(difficulty[j]);
                break;
            }
        }
    }

    return result;
};