826. Most Profit Assigning Work
: medium
У вас есть n заданий и m рабочих. Вам given три 数组а: difficulty, profit и worker, где:
difficulty[i] и profit[i] — Complexity и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со Complexityю не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
На示例, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.
return максимальную прибыль, которую можно получить после распределения рабочих по заданиям.
示例:
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 a profit of [20,20,30,30] separately.
C# 解法
匹配/原始public class Solution {
public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
var jobProfile = new List<int[]> { new int[] { 0, 0 } };
for (int i = 0; i < difficulty.Length; i++) {
jobProfile.Add(new int[] { difficulty[i], profit[i] });
}
jobProfile.Sort((a, b) => a[0].CompareTo(b[0]));
for (int i = 1; i < jobProfile.Count; i++) {
jobProfile[i][1] = Math.Max(jobProfile[i][1], jobProfile[i - 1][1]);
}
int netProfit = 0;
foreach (int ability in worker) {
int l = 0, r = jobProfile.Count - 1, jobProfit = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (jobProfile[mid][0] <= ability) {
jobProfit = Math.Max(jobProfit, jobProfile[mid][1]);
l = mid + 1;
} else {
r = mid - 1;
}
}
netProfit += jobProfit;
}
return netProfit;
}
}C++ 解法
自动草稿，提交前请检查#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MaxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
var jobProfile = new List<int[]> { new int[] { 0, 0 } };
for (int i = 0; i < difficulty.size(); i++) {
jobProfile.push_back(new int[] { difficulty[i], profit[i] });
}
jobProfile.Sort((a, b) => a[0].CompareTo(b[0]));
for (int i = 1; i < jobProfile.size(); i++) {
jobProfile[i][1] = max(jobProfile[i][1], jobProfile[i - 1][1]);
}
int netProfit = 0;
foreach (int ability in worker) {
int l = 0, r = jobProfile.size() - 1, jobProfit = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (jobProfile[mid][0] <= ability) {
jobProfit = max(jobProfit, jobProfile[mid][1]);
l = mid + 1;
} else {
r = mid - 1;
}
}
netProfit += jobProfit;
}
return netProfit;
}
}Java 解法
匹配/原始class Solution {
public int maxProfitAssignment(
int[] difficulty,
int[] profit,
int[] worker
) {
List<int[]> jobProfile = new ArrayList<>();
jobProfile.add(new int[] { 0, 0 });
for (int i = 0; i < difficulty.length; i++) {
jobProfile.add(new int[] { difficulty[i], profit[i] });
}
Collections.sort(jobProfile, (a, b) -> Integer.compare(a[0], b[0]));
for (int i = 0; i < jobProfile.size() - 1; i++) {
jobProfile.get(i + 1)[1] = Math.max(
jobProfile.get(i)[1],
jobProfile.get(i + 1)[1]
);
}
int netProfit = 0;
for (int i = 0; i < worker.length; i++) {
int ability = worker[i];
int l = 0, r = jobProfile.size() - 1, jobProfit = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (jobProfile.get(mid)[0] <= ability) {
jobProfit = Math.max(jobProfit, jobProfile.get(mid)[1]);
l = mid + 1;
} else {
r = mid - 1;
}
}
netProfit += jobProfit;
}
return netProfit;
}JavaScript 解法
匹配/原始var maxProfitAssignment = function(difficulty, profit, worker) {
let jobProfile = [[0, 0]];
for (let i = 0; i < difficulty.length; i++) {
jobProfile.push([difficulty[i], profit[i]]);
}
jobProfile.sort((a, b) => a[0] - b[0]);
for (let i = 1; i < jobProfile.length; i++) {
jobProfile[i][1] = Math.max(jobProfile[i][1], jobProfile[i - 1][1]);
}
let netProfit = 0;
for (let ability of worker) {
let l = 0, r = jobProfile.length - 1, jobProfit = 0;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
if (jobProfile[mid][0] <= ability) {
jobProfit = Math.max(jobProfit, jobProfile[mid][1]);
l = mid + 1;
} else {
r = mid - 1;
}
}
netProfit += jobProfit;
}
return netProfit;Python 解法
匹配/原始class Solution:
def maxProfitAssignment(self, difficulty, profit, worker):
jobProfile = [(0, 0)]
for i in range(len(difficulty)):
jobProfile.append((difficulty[i], profit[i]))
jobProfile.sort()
for i in range(1, len(jobProfile)):
jobProfile[i] = (jobProfile[i][0], max(jobProfile[i][1], jobProfile[i-1][1]))
netProfit = 0
for ability in worker:
l, r = 0, len(jobProfile) - 1
jobProfit = 0
while l <= r:
mid = (l + r) // 2
if jobProfile[mid][0] <= ability:
jobProfit = max(jobProfit, jobProfile[mid][1])
l = mid + 1
else:
r = mid - 1
netProfit += jobProGo 解法
匹配/原始func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
type Job struct {
Difficulty int
Profit int
}
jobProfile := []Job{{0, 0}}
for i := 0; i < len(difficulty); i++ {
jobProfile = append(jobProfile, Job{difficulty[i], profit[i]})
}
sort.Slice(jobProfile, func(i, j int) bool {
return jobProfile[i].Difficulty < jobProfile[j].Difficulty
})
for i := 1; i < len(jobProfile); i++ {
jobProfile[i].Profit = max(jobProfile[i].Profit, jobProfile[i-1].Profit)
}
netProfit := 0
for _, ability := range worker {
l, r := 0, len(jobProfile)-1
jobProfit := 0
for l <= r {
mid := (l + r) / 2
if jobProfile[mid].Difficulty <= ability {
jobProfit = max(jobProfit, jobProfile[mid].Profit)
l = mid + 1
} else {
r = mid - 1
}
}
netProfit += jobProfit
}
return netProfit
}
func max(a, b int) int {
if a > b {
return a
}
return b
}Algorithm
Создание и сортировка профиля работы
Инициализируйте 数组 пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.
Обновление максимальной прибыли для каждой сложности
Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли.
Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы find задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и return ее.
😎
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.