aboutsummaryrefslogtreecommitdiff
path: root/most_profit_assigning_work.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /most_profit_assigning_work.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'most_profit_assigning_work.py')
-rw-r--r--most_profit_assigning_work.py62
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]
+ )
+ )