[leetcode] 826. Most Profit Assigning Work

[leetcode] 826. Most profit Assigning Work

Description

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 <= 100001 <= worker.length <= 10000difficulty[i], profit[i], worker[i] are in range [1, 10^5]

分析

题目的意思是：给定工人workers能接受的difficulty，求在所有能接受的难度中选择收益最大的值.

先进行排序，然后对每个work一个一个的找到其最大profit就行了，如果没有想到用vector pair进行排序，可能就做不出来了。时间复杂度: O(NlogN+QlogQ)空间复杂度: O(N)

代码

class Solution {public: int maxProfitAssignment(vector& difficulty, vector& profit, vector& worker) { vector> jobs; int n=profit.size(); int res=0; for(int j=0;j=jobs[i].first){ mx=max(mx,jobs[i].second); i++; } res+=mx; } return res; }};

参考文献

​​826. Most Profit Assigning Work​​​​Most Profit Assigning Work 安排工作以达到最大收益​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。