aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-30 18:19:50 -0600
committerJack Sangdahl <[email protected]>2025-04-30 18:20:06 -0600
commit395ece1fa6936500eceb9e2ce825a653cafcba51 (patch)
tree815a0db19f1f07b9ad9f6a340eb187cf017829ae
parent8f773da1404a7c3f1e4a9ccde3d7b33c27d8c3be (diff)
downloadleetcode-395ece1fa6936500eceb9e2ce825a653cafcba51.tar.gz
leetcode-395ece1fa6936500eceb9e2ce825a653cafcba51.zip
2071. maximum number of tasks you can assignHEADmaster
-rw-r--r--max_num_tasks_assign.py64
1 files changed, 64 insertions, 0 deletions
diff --git a/max_num_tasks_assign.py b/max_num_tasks_assign.py
new file mode 100644
index 0000000..4c2fbf5
--- /dev/null
+++ b/max_num_tasks_assign.py
@@ -0,0 +1,64 @@
+# 2071. Maximum Number of Tasks You Can Assign
+from bisect import bisect_left
+
+"""
+you have 'n' tasks and 'm' workers. each task has a strength requirement
+stored in a 0-indexed integer array 'tasks', with the i'th task requiring
+'tasks[i]' strength to complete. the strength of each worker is stored in a
+0-indexed array 'workers' with the j'th worker having 'workers[j]' strength.
+each worker can only be assigned to a single task and must have a strength
+greather than or equal to the task's strength requirement. additionally, you
+have 'pills' magic pills that will increase a workers strength by 'strength'.
+you can decide which workers receive the pills, however, you may only give
+each worker at most one magical pill. given the 0-indexed integer arrays
+'tasks' and 'workers' and the integers 'pills' and 'strength', return the
+maximum number of tasks that can be completed.
+"""
+
+
+class Solution(object):
+ def maxTaskAssign(self, tasks, workers, pills, strength):
+ """
+ :type tasks: List[int]
+ :type workers: List[int]
+ :type pills: int
+ :type strength: int
+ :rtype: int
+ """
+
+ def check(k):
+ w, tries = workers[-k:], pills
+ for i in tasks[:k][::-1]:
+ idx = bisect_left(w, i)
+ if idx < len(w):
+ w.pop(idx)
+ elif tries > 0:
+ idx = bisect_left(w, i - strength)
+ if idx < len(w):
+ w.pop(idx)
+ tries -= 1
+ else:
+ return False
+ return len(w) == 0
+
+ tasks = sorted(tasks)
+ workers = sorted(workers)
+ l, r = 0, min(len(workers), len(tasks)) + 1
+ while l + 1 < r:
+ m = l + (r - l) // 2
+ if check(m):
+ l = m
+ else:
+ r = m
+ return l
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxTaskAssign(tasks=[3, 2, 1], workers=[0, 3, 3], pills=1, strength=1))
+ print(obj.maxTaskAssign(tasks=[5, 4], workers=[0, 0, 0], pills=1, strength=5))
+ print(
+ obj.maxTaskAssign(
+ tasks=[10, 15, 30], workers=[0, 10, 10, 10, 10], pills=3, strength=10
+ )
+ )