3476. 最大化任务分配的利润 🔒
题目描述
给定一个整数数组 workers，其中 workers[i] 表示第 i 个工人的技能等级。同时给定一个 2 维数组 tasks，其中：
tasks[i][0]表示完成任务所需的技能要求。tasks[i][1]表示完成任务的收益。
每一个工人 最多 能完成一个任务，并且只有在他们的技能等级 等于 任务的技能要求时才能获取此任务。今天又有一名 额外 工人加入，他可以承接任何任务，无论 技能要求如何。
返回按照最优方式分配任务给工人所能获得的 最大 总利润。
示例 1：
输入：workers = [1,2,3,4,5], tasks = [[1,100],[2,400],[3,100],[3,400]]
输出：1000
解释：
- 工人 0 完成任务 0。
- 工人 1 完成任务 1。
- 工人 2 完成任务 3。
- 额外工人完成任务 2。
示例 2：
输入：workers = [10,10000,100000000], tasks = [[1,100]]
输出：100
解释：
由于没有工人满足技能需求，只有额外工人能够完成任务 0。
示例 3：
输入：workers = [7], tasks = [[3,3],[3,3]]
输出：3
解释：
额外工人完成任务 1。由于没有任务的技能需求为 7，工人 0 无法工作。
提示：
1 <= workers.length <= 1051 <= workers[i] <= 1091 <= tasks.length <= 105tasks[i].length == 21 <= tasks[i][0], tasks[i][1] <= 109
解法
方法一：哈希表 + 优先队列
由于每个任务只能被一个特定技能的工人完成，因此，我们可以将任务按技能要求分组，放在一个哈希表 $\textit{d}$ 中，其中键是技能要求，值是一个优先队列，按照利润从大到小排序。
然后，我们遍历工人，对于每个工人，我们从哈希表 $\textit{d}$ 中找到其技能要求对应的优先队列，取出队首元素，即该工人能获得的最大利润，然后将其从优先队列中移除。如果优先队列为空，我们将其从哈希表中移除。
最后，我们将剩余任务中的最大利润加到结果中。
时间复杂度 $O((n + m) \times \log m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别是工人和任务的数量。
Python3
class Solution:
def maxProfit(self, workers: List[int], tasks: List[List[int]]) -> int:
d = defaultdict(SortedList)
for skill, profit in tasks:
d[skill].add(profit)
ans = 0
for skill in workers:
if not d[skill]:
continue
ans += d[skill].pop()
mx = 0
for ls in d.values():
if ls:
mx = max(mx, ls[-1])
ans += mx
return ans
Java
class Solution {
public long maxProfit(int[] workers, int[][] tasks) {
Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();
for (var t : tasks) {
int skill = t[0], profit = t[1];
d.computeIfAbsent(skill, k -> new PriorityQueue<>((a, b) -> b - a)).offer(profit);
}
long ans = 0;
for (int skill : workers) {
if (d.containsKey(skill)) {
var pq = d.get(skill);
ans += pq.poll();
if (pq.isEmpty()) {
d.remove(skill);
}
}
}
int mx = 0;
for (var pq : d.values()) {
mx = Math.max(mx, pq.peek());
}
ans += mx;
return ans;
}
}
C++
class Solution {
public:
long long maxProfit(vector<int>& workers, vector<vector<int>>& tasks) {
unordered_map<int, priority_queue<int>> d;
for (const auto& t : tasks) {
d[t[0]].push(t[1]);
}
long long ans = 0;
for (int skill : workers) {
if (d.contains(skill)) {
auto& pq = d[skill];
ans += pq.top();
pq.pop();
if (pq.empty()) {
d.erase(skill);
}
}
}
int mx = 0;
for (const auto& [_, pq] : d) {
mx = max(mx, pq.top());
}
ans += mx;
return ans;
}
};
Go
func maxProfit(workers []int, tasks [][]int) (ans int64) {
d := make(map[int]*hp)
for _, t := range tasks {
skill, profit := t[0], t[1]
if _, ok := d[skill]; !ok {
d[skill] = &hp{}
}
d[skill].push(profit)
}
for _, skill := range workers {
if _, ok := d[skill]; !ok {
continue
}
ans += int64(d[skill].pop())
if d[skill].Len() == 0 {
delete(d, skill)
}
}
mx := 0
for _, pq := range d {
for pq.Len() > 0 {
mx = max(mx, pq.pop())
}
}
ans += int64(mx)
return
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int { return heap.Pop(h).(int) }
TypeScript
function maxProfit(workers: number[], tasks: number[][]): number {
const d = new Map();
for (const [skill, profit] of tasks) {
if (!d.has(skill)) {
d.set(skill, new MaxPriorityQueue());
}
d.get(skill).enqueue(profit);
}
let ans = 0;
for (const skill of workers) {
const pq = d.get(skill);
if (pq) {
ans += pq.dequeue();
if (pq.size() === 0) {
d.delete(skill);
}
}
}
let mx = 0;
for (const pq of d.values()) {
mx = Math.max(mx, pq.front());
}
ans += mx;
return ans;
}