跳转至

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 <= 105
  • 1 <= workers[i] <= 109
  • 1 <= tasks.length <= 105
  • tasks[i].length == 2
  • 1 <= tasks[i][0], tasks[i][1] <= 109

解法

方法一：哈希表 + 优先队列

由于每个任务只能被一个特定技能的工人完成，因此，我们可以将任务按技能要求分组，放在一个哈希表 \(\textit{d}\) 中，其中键是技能要求，值是一个优先队列，按照利润从大到小排序。

然后，我们遍历工人，对于每个工人，我们从哈希表 \(\textit{d}\) 中找到其技能要求对应的优先队列，取出队首元素，即该工人能获得的最大利润，然后将其从优先队列中移除。如果优先队列为空，我们将其从哈希表中移除。

最后，我们将剩余任务中的最大利润加到结果中。

时间复杂度 \(O((n + m) \times \log m)\)，空间复杂度 \(O(m)\)。其中 \(n\) 和 \(m\) 分别是工人和任务的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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

 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
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;
    }
}

 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
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;
    }
};

 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
30
31
32
33
34
35
36
37
38
39
40
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) }

 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
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;
}

评论