0826. Most Profit Assigning Work

题目信息

题号:

0826

难度:

Medium

主题:

任务分配、能力限制、最大利润

原题:

LeetCode 0826

重点:

每名工人至多完成一个难度不超过自身能力的工作;同一种工作可以被多名工人重复选择

题目重述

数组 difficulty 和 profit 描述若干种工作,第 i 种工作的难度为 difficulty[i],完成一次可获得 profit[i]。数组 worker 给出每名工人的能力值。

每名工人至多选择一种难度不超过其能力的工作,也可以不工作;同一种工作没有人数上限,可以由多名工人分别完成并各自获得利润。请返回合理分配后所有工人能够获得的最大总利润。

difficulty.length == profit.length,工作种数和工人数均在 [1, 10^4] 范围内;难度、利润和能力值均在 [1, 10^5] 范围内。

自建示例

同一工作可以重复分配:

输入:difficulty = [2,5], profit = [10,30], worker = [1,2,6,6]
输出:70
解释:能力 1 的工人无法工作,能力 2 的工人选择利润 10 的工作,两名能力 6 的工人都可选择利润 30 的工作,总利润为 0 + 10 + 30 + 30 = 70。

所有工人能力都不足:

输入:difficulty = [8], profit = [50], worker = [1]
输出:0
解释:工作种数和工人数都达到允许的最小值,但唯一工人的能力 1 小于工作难度 8,无法完成任何工作,因此最大总利润为 0。