Problem
We have jobs: difficulty[i]
is the difficulty of the i
th job, and profit[i]
is the profit of the i
th job.
Now we have some workers. worker[i]
is the ability of the i
th 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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua // Running time: 90 ms class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) { const int n = difficulty.size(); vector<pair<int, int>> jobs; // difficulty, profit for (int i = 0; i < n; ++i) jobs.emplace_back(difficulty[i], profit[i]); std::sort(jobs.begin(), jobs.end()); std::sort(worker.begin(), worker.end()); int ans = 0; int i = 0; int best = 0; for (int level : worker) { while (i < n && level >= jobs[i].first) best = max(best, jobs[i++].second); ans += best; } return ans; } }; |
Solution 2: Bucket + Greedy
Key idea: for each difficulty D, find the most profit job whose requirement is <= D.
Three steps:
- for each difficulty D, find the most profit job whose requirement is == D, best[D] = max{profit of difficulty D}.
- if difficulty D – 1 can make more profit than difficulty D, best[D] = max(best[D], best[D – 1]).
- The max profit each worker at skill level D can make is best[D].
Time complexity: O(n)
Space complexity: O(10000)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 112 ms class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) { const int N = 100000; // max profit at difficulty i vector<int> max_profit(N + 1, 0); for (int i = 0; i < difficulty.size(); ++i) max_profit[difficulty[i]] = max(max_profit[difficulty[i]], profit[i]); for (int i = 2; i <= N; ++i) max_profit[i] = max(max_profit[i], max_profit[i - 1]); int ans = 0; for (int level : worker) ans += max_profit[level]; return ans; } }; |
C++ using map
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 112 ms class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) { map<int, int> bests; for (int i = 0; i < difficulty.size(); ++i) bests[difficulty[i]] = max(bests[difficulty[i]], profit[i]); int best = 0; for (auto it = bests.begin(); it != bests.end(); ++it) it->second = best = max(it->second, best); int ans = 0; for (int level : worker) ans += prev(bests.upper_bound(level))->second; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment