Press "Enter" to skip to content

花花酱 LeetCode 826. Most Profit Assigning Work

Problem

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]

Solution 1: Sorting + Two pointers

Time complexity: O(nlogn + mlogm)

Space complexity: O(n)

Solution 2: Bucket + Greedy

Key idea: for each difficulty D, find the most profit job whose requirement is <= D.

Three steps:

  1. for each difficulty D, find the most profit job whose requirement is == D, best[D] = max{profit of difficulty D}.
  2. if difficulty D – 1 can make more profit than difficulty D, best[D] = max(best[D], best[D – 1]).
  3. The max profit each worker at skill level D can make is best[D].

Time complexity: O(n)

Space complexity: O(10000)

C++

 

C++ using map

 

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply