Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

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: 跟IPO那題很像
→ sustainer123: 對 所以我用一樣方法
→ sustainer123: 只是我猜這題不用壓在nlogn
推 JIWP: 感覺一定要排序
→ JIWP: 不過可以不用heap
推 DJYOSHITAKA: 大濕...
→ sustainer123: 改用指針紀錄吧 我猜
推 JIWP: 你就一直紀錄到目前的max值就好
→ Rushia: HEAP和排序複雜度又沒差= =