题目描述：

LeetCode 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]

题目大意：

给定一组任务的难度difficulty及其收益profit，有一组工人最多可以处理难度为worker的任务。

每一个任务可以执行多次，每一个工人只能执行一个任务，求最大总收益。

解题思路：

贪心（Greedy Algorithm）

每个工人都选择不大于其难度上限的最大收益的任务

问题即转化为求范围内的最大值

Python代码:

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        """
        :type difficulty: List[int]
        :type profit: List[int]
        :type worker: List[int]
        :rtype: int
        """
        diffPro = collections.defaultdict(int)
        for diff, pro in zip(difficulty, profit):
            diffPro[diff] = max(diffPro[diff], pro)
        maxVal = 0
        for x in range(min(difficulty + worker), max(difficulty + worker) + 1):
            diffPro[x] = max(diffPro[x], maxVal)
            maxVal = max(diffPro[x], maxVal)
        return sum(diffPro[w] for w in worker)

 

本文链接：http://bookshadow.com/weblog/2018/04/29/leetcode-most-profit-assigning-work/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码