有一些工作:difficulty[i] 表示第 i 个工作的难度,profit[i] 表示第 i 个工作的收益。
现在我们有一些工人。worker[i] 是第 i 个工人的能力,即该工人只能完成难度小于等于 worker[i] 的工作。
每一个工人都最多只能安排一个工作,但是一个工作可以完成多次。
举个例子,如果 3 个工人都尝试完成一份报酬为 1 的同样工作,那么总收益为 $3。如果一个工人不能完成任何工作,他的收益为 $0 。
我们能得到的最大收益是多少?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/most-profit-assigning-work
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public static int maxProfitAssignment0(int[] difficulty, int[] profit, int[] worker) {
Arrays.sort(worker);
PriorityQueue<Integer> difficultyQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(difficulty[o1], difficulty[o2]);
}
});
PriorityQueue<Integer> profitQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(profit[o2], profit[o1]);
}
});
for (int i = 0; i < difficulty.length; ++i) {
difficultyQueue.offer(i);
}
int ret = 0;
for (int i = 0; i < worker.length; ++i) {
while (!difficultyQueue.isEmpty() && difficulty[difficultyQueue.peek()] <= worker[i]) {
profitQueue.offer(difficultyQueue.poll());
}
ret += profitQueue.isEmpty() ? 0 : profit[profitQueue.peek()];
}
return ret;
}
public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
Job[] jobs = new Job[difficulty.length];
for (int i = 0; i < difficulty.length; ++i) {
jobs[i] = new Job(difficulty[i], profit[i]);
}
Arrays.sort(jobs, new Comparator<Job>() {
@Override
public int compare(Job o1, Job o2) {
return o1.difficulty == o2.difficulty ? Integer.compare(o2.profit, o1.profit) : Integer.compare(o1.difficulty, o2.difficulty);
}
});
Arrays.sort(worker);
int ret = 0;
int index = 0, best = 0;
for (int i = 0; i < worker.length; ++i) {
while (index < jobs.length && jobs[index].difficulty <= worker[i]) {
best = Math.max(best, jobs[index].profit);
index++;
}
ret += best;
}
return ret;
}
}
class Job {
int difficulty;
int profit;
public Job(int difficulty, int profit) {
this.difficulty = difficulty;
this.profit = profit;
}
}