Daily Leetcode 826. Most Profit Assigning Work

https://leetcode.com/problems/most-profit-assigning-work/

Medium

问题描述：

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,thenthetotalprofitwillbe1,thenthetotalprofitwillbe3. 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，difficulty[i]表示ith任务的难度，profit[i]表示ith任务的报酬，而worker[i]表示ith员工的工作能力，当工作能力大于工作难度时，才能够胜任该任务。我们需要规划工作方案，得到最大的利润值。

这一题显然可以使用贪心策略，由于工作难度与报酬是一一对应的，我们可以使用zip方法将它们组合成一个二维list，并且按工作难度升序排序；再对工人按工作能力进行升序排序。得到job数组和排过序的worker数组，这样，我们只需要遍历一次worker数组，为每一个工人选择它能力范围内最高报酬的工作，就能够得到当前情况下的最大利润值。

代码：

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        """
        :type difficulty: List[int]
        :type profit: List[int]
        :type worker: List[int]
        :rtype: int
        """
        res = i = currentBest = 0
        job = sorted(zip(difficulty, profit), key = lambda t: t[0])
        
        for ability in sorted(worker):
            while i < len(job) and ability >= job[i][0]:
                currentBest = max(currentBest, job[i][1])
                i += 1
            res += currentBest

        return res