Re: [閒聊] 每日leetcode

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/06/18 10:40)推噓3(3推 0噓 6→)

留言9則, 4人參與討論串377/1549 (看更多)

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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.84 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718678447.A.C79.html

→

JIWP

06/18 10:42, 1年前 , 1^F

06/18 10:42, 1^F

→

sustainer123

06/18 10:43, 1年前 , 2^F

06/18 10:43, 2^F

→

sustainer123

06/18 10:43, 1年前 , 3^F

06/18 10:43, 3^F