826. Most Profit Assigning Work
1. 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?
2. Example
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.
3. Note
- 1 <= difficulty.length = profit.length <= 10000
- 1 <= worker.length <= 10000
- difficulty[i], profit[i], worker[i] are in range [1, $10^5$]
4. Solutions
My Accepted Solution
m = range($10^5$), n = i_difficulty.size(), o = i_worker.size()
Time complexity: O(m + n + o)
Space complexity: O(m)
// Bucket and Greedy
// If the range of difficulty and worker is not very big, we could use the bucket and the greedy
// algorithm. For the greedy algorithm, we try to get the best profit for every worker. So, we
// define maxProfitAtDifficulty, which means at a specific difficulty, how many profits can we get.
// After we get the best profits for all difficulties, we insert the empty difficulties because not
// every difficulty has a profit. So we set the profit of an empty difficulty with the best profit
// whose difficulty less than the empty one. Then, as we know every difficulty's best profit, we
// just iterate all workers and get the worker's best profit, then sum them up.
class Solution {
public:
// int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker)
int maxProfitAssignment(
const vector<int>& i_difficulty,
const vector<int>& i_profit,
const vector<int>& i_worker) {
vector<int> maxProfitAtDifficulty(
10001); // the value range of difficulty and worker is [1, 10000]
for (int i = 0; i < i_difficulty.size(); ++i) {
maxProfitAtDifficulty[i_difficulty[i]] =
max(i_profit[i], maxProfitAtDifficulty[i_difficulty[i]]);
}
for (int i = 0, maxProfit = 0; i < maxProfitAtDifficulty.size(); ++i) {
maxProfit = max(maxProfitAtDifficulty[i], maxProfit);
maxProfitAtDifficulty[i] = max(maxProfit, maxProfitAtDifficulty[i]);
}
int maxProfits = 0;
for (auto ability : i_worker) {
maxProfits += maxProfitAtDifficulty[ability];
}
return maxProfits;
}
};
m = i_difficulty.size(), n = i_worker.size()
Time complexity: O($mlog_2m + nlog_2n$)
Space complexity: O(m)
// Sort, Two Pointers and Greedy
// We sort the pair<profit, difficulty> by the profit because we want to get the best profits. Then,
// we sort workers by their abilities. So, for every worker with a given ability, we find the job
// with the best profit he can handle, which means its difficulty is less than the worker's ability.
class Solution {
public:
// int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker)
int maxProfitAssignment(
const vector<int>& i_difficulty,
const vector<int>& i_profit,
vector<int>& m_worker) {
vector<pair<int, int>> profitsDifficulties;
for (int i = 0; i < i_difficulty.size(); ++i) {
profitsDifficulties.emplace_back(i_profit[i], i_difficulty[i]);
}
sort(profitsDifficulties.begin(), profitsDifficulties.end(), greater<pair<int, int>>());
sort(m_worker.begin(), m_worker.end(), greater<int>());
int maxProfits = 0;
for (int workerIndex = 0, profitIndex = 0; workerIndex < m_worker.size(); ++workerIndex) {
while (profitIndex < profitsDifficulties.size() &&
m_worker[workerIndex] < profitsDifficulties[profitIndex].second) {
++profitIndex;
}
if (profitIndex < profitsDifficulties.size()) {
maxProfits += profitsDifficulties[profitIndex].first;
}
}
return maxProfits;
}
};