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]

分析：
每个人有一个能力值，只能做难度低于自身能力值的工作，每个工作有报酬，设计一个方法让报酬最大，注意数据长度为10000，数据值不超过100000，这说明复杂度n^2是不行的

思路：
用动态规划思想，dp[i]表示能力值为i的工人最多能拿多少报酬，i最多不超过100000，所以空间不会超出，那么结果就是sum(dp[i] for i in worker)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxProfitAssignment(difficulty, profit, worker):
    d = collections.defaultdict(int)
    key = set(difficulty)
    dp = [0] * (max(worker)+1)
    # 可能存在相同困难度的工作有不同的报酬，这里只将最高的报酬记录
    for i in range(len(difficulty)):
        d[difficulty[i]] = max(d[difficulty[i]], profit[i])

    for i in range(1,len(dp)):
        if i in key:
            dp[i] = max(dp[i-1],d[i])
        else:
            dp[i] = dp[i-1]

    res = 0
    for i in range(len(worker)):
        res += dp[worker[i]]
    return res

"difficulty: medium
57 / 57 test cases passed
runtime: 559 ms"