| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
|
你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:
difficulty[i]表示第i个工作的难度，profit[i]表示第i个工作的收益。worker[i]是第i个工人的能力，即该工人只能完成难度小于等于worker[i]的工作。
每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。
- 举个例子，如果 3 个工人都尝试完成一份报酬为
$1的同样工作，那么总收益为$3。如果一个工人不能完成任何工作，他的收益为$0。
返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。
示例 1：
输入: 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] 的收益。
示例 2:
输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25] 输出: 0
提示:
n == difficulty.lengthn == profit.lengthm == worker.length1 <= n, m <= 1041 <= difficulty[i], profit[i], worker[i] <= 105
我们可以将工作按照能力升序排列，然后将工作按照难度升序排列。
然后我们遍历工人，对于每个工人，我们找出他能完成的工作中收益最大的那个，然后将这个收益加到答案中。
时间复杂度 profit 和 worker 的长度。
class Solution:
def maxProfitAssignment(
self, difficulty: List[int], profit: List[int], worker: List[int]
) -> int:
worker.sort()
jobs = sorted(zip(difficulty, profit))
ans = mx = i = 0
for w in worker:
while i < len(jobs) and jobs[i][0] <= w:
mx = max(mx, jobs[i][1])
i += 1
ans += mx
return ansclass Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
Arrays.sort(worker);
int n = profit.length;
int[][] jobs = new int[n][0];
for (int i = 0; i < n; ++i) {
jobs[i] = new int[] {difficulty[i], profit[i]};
}
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
int ans = 0, mx = 0, i = 0;
for (int w : worker) {
while (i < n && jobs[i][0] <= w) {
mx = Math.max(mx, jobs[i++][1]);
}
ans += mx;
}
return ans;
}
}class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
sort(worker.begin(), worker.end());
int n = profit.size();
vector<pair<int, int>> jobs;
for (int i = 0; i < n; ++i) {
jobs.emplace_back(difficulty[i], profit[i]);
}
sort(jobs.begin(), jobs.end());
int ans = 0, mx = 0, i = 0;
for (int w : worker) {
while (i < n && jobs[i].first <= w) {
mx = max(mx, jobs[i++].second);
}
ans += mx;
}
return ans;
}
};func maxProfitAssignment(difficulty []int, profit []int, worker []int) (ans int) {
sort.Ints(worker)
n := len(profit)
jobs := make([][2]int, n)
for i, p := range profit {
jobs[i] = [2]int{difficulty[i], p}
}
sort.Slice(jobs, func(i, j int) bool { return jobs[i][0] < jobs[j][0] })
mx, i := 0, 0
for _, w := range worker {
for ; i < n && jobs[i][0] <= w; i++ {
mx = max(mx, jobs[i][1])
}
ans += mx
}
return
}function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
const n = profit.length;
worker.sort((a, b) => a - b);
const jobs = Array.from({ length: n }, (_, i) => [difficulty[i], profit[i]]);
jobs.sort((a, b) => a[0] - b[0]);
let [ans, mx, i] = [0, 0, 0];
for (const w of worker) {
while (i < n && jobs[i][0] <= w) {
mx = Math.max(mx, jobs[i++][1]);
}
ans += mx;
}
return ans;
}我们不妨记
然后我们遍历工作，对于每个工作
接下来，我们从
最后，我们遍历工人，对于每个工人
时间复杂度 profit 的长度，而 difficulty 中的最大值。
class Solution:
def maxProfitAssignment(
self, difficulty: List[int], profit: List[int], worker: List[int]
) -> int:
m = max(difficulty)
f = [0] * (m + 1)
for d, p in zip(difficulty, profit):
f[d] = max(f[d], p)
for i in range(1, m + 1):
f[i] = max(f[i], f[i - 1])
return sum(f[min(w, m)] for w in worker)class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int m = Arrays.stream(difficulty).max().getAsInt();
int[] f = new int[m + 1];
int n = profit.length;
for (int i = 0; i < n; ++i) {
int d = difficulty[i];
f[d] = Math.max(f[d], profit[i]);
}
for (int i = 1; i <= m; ++i) {
f[i] = Math.max(f[i], f[i - 1]);
}
int ans = 0;
for (int w : worker) {
ans += f[Math.min(w, m)];
}
return ans;
}
}class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int m = *max_element(begin(difficulty), end(difficulty));
int f[m + 1];
memset(f, 0, sizeof(f));
int n = profit.size();
for (int i = 0; i < n; ++i) {
int d = difficulty[i];
f[d] = max(f[d], profit[i]);
}
for (int i = 1; i <= m; ++i) {
f[i] = max(f[i], f[i - 1]);
}
int ans = 0;
for (int w : worker) {
ans += f[min(w, m)];
}
return ans;
}
};func maxProfitAssignment(difficulty []int, profit []int, worker []int) (ans int) {
m := slices.Max(difficulty)
f := make([]int, m+1)
for i, d := range difficulty {
f[d] = max(f[d], profit[i])
}
for i := 1; i <= m; i++ {
f[i] = max(f[i], f[i-1])
}
for _, w := range worker {
ans += f[min(w, m)]
}
return
}function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
const m = Math.max(...difficulty);
const f = Array(m + 1).fill(0);
const n = profit.length;
for (let i = 0; i < n; ++i) {
const d = difficulty[i];
f[d] = Math.max(f[d], profit[i]);
}
for (let i = 1; i <= m; ++i) {
f[i] = Math.max(f[i], f[i - 1]);
}
return worker.reduce((acc, w) => acc + f[Math.min(w, m)], 0);
}