diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /most_profit_assigning_work.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'most_profit_assigning_work.py')
-rw-r--r-- | most_profit_assigning_work.py | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/most_profit_assigning_work.py b/most_profit_assigning_work.py new file mode 100644 index 0000000..7fb258b --- /dev/null +++ b/most_profit_assigning_work.py @@ -0,0 +1,62 @@ +# 826. Most Profit Assigning Work + +""" +you have n jobs and m workers. you are given three arrays: difficulty, +profit, and worker where difficulty and pofit are the difficulty and profit +of the i'th job and worker is the ability of the jth worker. every worker can +be assigned at most one job, but one job can be completed multiple times. +return the maximum profit we can achieve after assigning the workers to the +jobs. +""" + + +class Solution(object): + def maxProfitAssignment(self, difficulty, profit, worker): + """ + :type difficulty: List[int] + :type profit: List[int] + :type worker: List[int] + :rtype: int + """ + max_profit_difficulty = [] + info = list(zip(difficulty, profit)) + info.sort(key=lambda x: x[0]) + max_p = 0 + for i in info: + d, p = i + max_p = max(max_p, p) + max_profit_difficulty.append((d, max_p)) + + def bin_search(l, upperbound): + i, j = 0, len(l) - 1 + while i < j: + mid = (i + j) // 2 + 1 + if l[mid][0] <= upperbound: + i = mid + else: + j = mid - 1 + return i + + total_profit = 0 + for w in worker: + idx = bin_search(max_profit_difficulty, w) + d, p = max_profit_difficulty[idx] + if w >= d: + total_profit += p + return total_profit + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maxProfitAssignment( + difficulty=[2, 4, 6, 8, 10], + profit=[10, 20, 30, 40, 50], + worker=[4, 5, 6, 7], + ) + ) + print( + obj.maxProfitAssignment( + difficulty=[85, 47, 57], profit=[24, 66, 99], worker=[40, 25, 25] + ) + ) |