0826. Most Profit Assigning Work¶
题目信息¶
- 题号:
0826
- 难度:
Medium
- 主题:
任务分配、能力限制、最大利润
- 原题:
- 重点:
每名工人至多完成一个难度不超过自身能力的工作;同一种工作可以被多名工人重复选择
题目重述¶
数组 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。