难度：★★★☆☆
类型：数组
方法：排序

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

有一些工作：difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。

现在我们有一些工人。worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。

举个例子，如果 3 个工人都尝试完成一份报酬为 1 的同样工作，那么总收益为 0 。

我们能得到的最大收益是多少？

示例：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

提示:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] 的范围是 [1, 10^5]

解答

这道题乍一看是背包问题，很容易联想到用动态规划解决，但实际上又有不同。

每个工作有两个属性，难度和收益，每个工人有一个属性，即工作能力。工作和工人是两个对象（object），这两个对象建立连接的方式是一条规则，即每个工人可以胜任自己能力范围之内的事情，用数学的语言来描述这个问题：

maximize(sum(profit_j))
s.t. ability_i >= difficulty_j

其中profit_i表示的是为每个工人挑选的工作的收益，约束条件是每个工人的能力ability_i >= 该工人承担的工作难度difficulty_j，因此这个问题就是约束条件下的优化问题，优化目标是最大化收益。

我们把所有工作按照难度排序，把所有工人按照能力排序，排序的好处是，可以经过一次遍历实现任务判断与分配。只排序工作或者只排序工作能力都不能满足这个任务，因此需要都进行排序。

排序完成后，就可以按照能力从低到高的顺序为各个工人i分配工作了。一个工人来挑选工作，难度从低到高寻找，直到找到刚好没有超过工人i能力的工作，在所有该工人可以胜任的工作中，选择收益最大的工作提供给该工人即可。这里我们使用一个中间变量best用来记录不超过当前难度的所有工作中收益最大的那个，作为每个工人挑选工作的依据。这道题的简单之处在于，工作是可以被重复做的，如果不能重复做可能又要使用别的办法。

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobs = sorted(zip(difficulty, profit))
        worker = sorted(worker)
        ans = index = best = 0
        for ability in worker:
            while index < len(jobs) and ability >= jobs[index][0]:
                best = max(best, jobs[index][1])
                index += 1
            ans += best
        return ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析