友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
826. 安排工作以达到最大收益
你有 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.length -
n == profit.length -
m == worker.length -
1 <= n, m <= 104 -
1 <= difficulty[i], profit[i], worker[i] <= 105
思路分析
先将 worker 排序，然后对 profit 和 difficulty 排序： profit 优先，相同则再根据 difficulty 排序。从后向前遍历 worker，只要 difficulty 满足，优先取获利最大的工作。
| 有点蒙对的感觉。不如题解更有说服力。 |
-
一刷
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
26
27
28
29
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-19 21:59:47
*/
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
Arrays.sort(worker);
int n = difficulty.length;
int m = worker.length;
Integer[] index = new Integer[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
// 这样能通过验证，但是感觉有点蒙对了的感觉。
Arrays.sort(index,
Comparator.comparingInt((Integer a) -> profit[a])
.thenComparingInt(a -> difficulty[a]));
int result = 0;
int idx = n - 1;
for (int i = m - 1; i >= 0; i--) {
while (idx >= 0 && difficulty[index[idx]] > worker[i]) {
idx--;
}
if (idx >= 0) {
result += profit[index[idx]];
}
}
return result;
}