https://leetcode.com/problems/most-profit-assigning-work
826. Most Profit Assigning Work
你有n份工作与m个工人
给定三数列
difficulty[i]与profit[i]代表第i份工作的收益与困难度
worker[j]代表工人的能力
工人只能接受困难度小于等于自己能力的工作
每位工人只能接一份工作 但工作能被重复完成
请回传我们将工作分配给工人后能获得的最大收益
Example 1:
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.
Example 2:
Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0
Constraints:
n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 104
1 <= difficulty[i], profit[i], worker[i] <= 105
思路:
排序 建max_heap
时间复杂度是nlogn
不知道能不能省下排序
Python Code:
class Solution:
def maxProfitAssignment(self, difficulty: List[int], profit: List[int],
worker: List[int]) -> int:
worker.sort()
n = sorted(list(zip(difficulty, profit)))
result = 0
max_heap = []
flag = -1
cur = 0
for w in worker:
while len(n) > cur:
if n[cur][0] > w:
break
heapq.heappush(max_heap,n[cur][1]*flag)
cur += 1
if max_heap:
x = heapq.heappop(max_heap)
print(x)
result += x * flag
heapq.heappush(max_heap,x)
return result