题目描述
有一些工作:difficulty[i]
表示第 i
个工作的难度,profit[i]
表示第 i
个工作的收益。
现在我们有一些工人。worker[i]
是第 i
个工人的能力,即该工人只能完成难度小于等于 worker[i]
的工作。
每一个工人都最多只能安排一个工作,但是一个工作可以完成多次。
举个例子,如果 3
个工人都尝试完成一份报酬为 $1
的同样工作,那么总收益为 $3
。如果一个工人不能完成任何工作,他的收益为 $0
。
我们能得到的最大收益是多少?
样例
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ,分别获得 [20,20,30,30] 的收益。
注意
1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i]
的范围是[1, 10^5]
算法1
(哈希数组) $O(n + m)$
- 将每个难度对应的报酬存在一个长度为 10^5 的数组
d
中。 - 如果每个难度对应多个不同的报酬,则取最大的报酬。
- 将其变为前缀最大值数组,即对每个
i
进行d[i] = max(d[i], d[i - 1])
。 - 对每个工人的
worker[i]
,累计d[worker[i]]
即可。
时间复杂度
- 假设 m 为最大的难度值,统计每个难度值最大的报酬需要 $O(n + m)$ 的时间,对于每个询问只需要 $O(1)$ 的时间。
- 总时间复杂度为 $O(n + m)$。
空间复杂度
- 需要额外的数组来存储
d
,故空间复杂度为 $O(m)$。
C++ 代码
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
vector<int> d(100001, 0);
int n = difficulty.size();
for (int i = 0; i < n; i++)
d[difficulty[i]] = max(d[difficulty[i]], profit[i]);
for (int i = 1; i <= 100000; i++)
d[i] = max(d[i], d[i - 1]);
int ans = 0;
for (auto &w : worker)
ans += d[w];
return ans;
}
};
算法2
(排序) $O(n \log n + q \log q)$
- 将难度和报酬的数对从小到大排序,难度为第一关键字。
- 将
worker
数组从小到大排序,然后遍历worker
数组,遍历过程中,记录小于等于当前worker[i]
的最大难度值下标j
,以及对应的最大报酬maxp
。 - 每次更新
j
和maxp
即可。
时间复杂度
- 排序的时间复杂度为 $O(n \log n + q \log q)$,询问只需要扫一遍,每个难度值最多也遍历一次,故这一部分的时间复杂度为 $O(n + q)$。
- 总时间复杂度为 $O(n \log n + q \log q)$。
空间复杂度
- 由于需要新数组来存储数对,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
vector<pair<int, int>> pr;
int n = difficulty.size();
for (int i = 0; i < n; i++)
pr.emplace_back(difficulty[i], profit[i]);
sort(pr.begin(), pr.end());
sort(worker.begin(), worker.end());
int j = 0, maxp = pr[0].second;
int ans = 0;
for (auto &w : worker) {
while (j < n && w >= pr[j + 1].first) {
j++;
maxp = max(maxp, pr[j].second);
}
if (w >= pr[j].first)
ans += maxp;
}
return ans;
}
};