826. Most Profit Assigning Work

描述

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

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 profit of [20,20,30,30] seperately.

Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i]  are in range [1, 10^5]

解法

思路比较简单，贪心即可，每个工人做他所能做的收益最大的工作。因此对输入进行预处理，把难度和收益组合起来按照收益从小到大进行排序，把工人按照能力从小到大排序。

写出来的第一版代码：

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        if not any([difficulty, profit, worker]):
            return 0

        m = dict(zip(difficulty, profit))
        sorted_tuple = sorted(m.items(), key=lambda x: x[1])
        worker.sort()
        di = len(sorted_tuple) - 1
        wi = len(worker) - 1

        profit = 0

        while wi >= 0 and di >= 0:
            if worker[wi] >= sorted_tuple[di][0]:
                profit += sorted_tuple[di][1]
                wi -= 1
            else:
                di -= 1

        return profit

这段代码在如下测试用例失败了：

[66,1,28,73,53,35,45,60,100,44,59,94,27,88,7,18,83,18,72,63]
[66,20,84,81,56,40,37,82,53,45,43,96,67,27,12,54,98,19,47,77]
[61,33,68,38,63,45,1,10,53,23,66,70,14,51,94,18,28,78,100,16]

原因是合并成字典的时候难度值出现了重复，因为字典的键唯一，所以重复的难度被更改为了第二次出现的收益。

其实此处不需要字典，把 zip 生成器转换成列表即可。

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        if not any([difficulty, profit, worker]):
            return 0

        sorted_tuple = sorted(list(zip(difficulty, profit)), key=lambda x: x[1])
        worker.sort()
        di = len(sorted_tuple) - 1
        wi = len(worker) - 1

        profit = 0

        while wi >= 0 and di >= 0:
            if worker[wi] >= sorted_tuple[di][0]:
                profit += sorted_tuple[di][1]
                wi -= 1
            else:
                di -= 1

        return profit