Welcome to Subscribe On Youtube
2071. Maximum Number of Tasks You Can Assign
Description
You have n
tasks and m
workers. Each task has a strength requirement stored in a 0indexed integer array tasks
, with the i^{th}
task requiring tasks[i]
strength to complete. The strength of each worker is stored in a 0indexed integer 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 greater than or equal to the task's strength requirement (i.e., workers[j] >= tasks[i]
).
Additionally, you have pills
magical pills that will increase a worker's strength by strength
. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill.
Given the 0indexed integer arrays tasks
and workers
and the integers pills
and strength
, return the maximum number of tasks that can be completed.
Example 1:
Input: tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1 Output: 3 Explanation: We can assign the magical pill and tasks as follows:  Give the magical pill to worker 0.  Assign worker 0 to task 2 (0 + 1 >= 1)  Assign worker 1 to task 1 (3 >= 2)  Assign worker 2 to task 0 (3 >= 3)
Example 2:
Input: tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5 Output: 1 Explanation: We can assign the magical pill and tasks as follows:  Give the magical pill to worker 0.  Assign worker 0 to task 0 (0 + 5 >= 5)
Example 3:
Input: tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10 Output: 2 Explanation: We can assign the magical pills and tasks as follows:  Give the magical pill to worker 0 and worker 1.  Assign worker 0 to task 0 (0 + 10 >= 10)  Assign worker 1 to task 1 (10 + 10 >= 15) The last pill is not given because it will not make any worker strong enough for the last task.
Constraints:
n == tasks.length
m == workers.length
1 <= n, m <= 5 * 10^{4}
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10^{9}
Solutions

class Solution { private int[] tasks; private int[] workers; private int strength; private int pills; private int m; private int n; public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) { Arrays.sort(tasks); Arrays.sort(workers); this.tasks = tasks; this.workers = workers; this.strength = strength; this.pills = pills; n = tasks.length; m = workers.length; int left = 0, right = Math.min(m, n); while (left < right) { int mid = (left + right + 1) >> 1; if (check(mid)) { left = mid; } else { right = mid  1; } } return left; } private boolean check(int x) { int i = 0; Deque<Integer> q = new ArrayDeque<>(); int p = pills; for (int j = m  x; j < m; ++j) { while (i < x && tasks[i] <= workers[j] + strength) { q.offer(tasks[i++]); } if (q.isEmpty()) { return false; } if (q.peekFirst() <= workers[j]) { q.pollFirst(); } else if (p == 0) { return false; } else { p; q.pollLast(); } } return true; } }

class Solution { public: int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { sort(tasks.begin(), tasks.end()); sort(workers.begin(), workers.end()); int n = tasks.size(), m = workers.size(); int left = 0, right = min(m, n); auto check = [&](int x) { int p = pills; deque<int> q; int i = 0; for (int j = m  x; j < m; ++j) { while (i < x && tasks[i] <= workers[j] + strength) { q.push_back(tasks[i++]); } if (q.empty()) { return false; } if (q.front() <= workers[j]) { q.pop_front(); } else if (p == 0) { return false; } else { p; q.pop_back(); } } return true; }; while (left < right) { int mid = (left + right + 1) >> 1; if (check(mid)) { left = mid; } else { right = mid  1; } } return left; } };

class Solution: def maxTaskAssign( self, tasks: List[int], workers: List[int], pills: int, strength: int ) > int: def check(x): i = 0 q = deque() p = pills for j in range(m  x, m): while i < x and tasks[i] <= workers[j] + strength: q.append(tasks[i]) i += 1 if not q: return False if q[0] <= workers[j]: q.popleft() elif p == 0: return False else: p = 1 q.pop() return True n, m = len(tasks), len(workers) tasks.sort() workers.sort() left, right = 0, min(n, m) while left < right: mid = (left + right + 1) >> 1 if check(mid): left = mid else: right = mid  1 return left

func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int { sort.Ints(tasks) sort.Ints(workers) n, m := len(tasks), len(workers) left, right := 0, min(m, n) check := func(x int) bool { p := pills q := []int{} i := 0 for j := m  x; j < m; j++ { for i < x && tasks[i] <= workers[j]+strength { q = append(q, tasks[i]) i++ } if len(q) == 0 { return false } if q[0] <= workers[j] { q = q[1:] } else if p == 0 { return false } else { p q = q[:len(q)1] } } return true } for left < right { mid := (left + right + 1) >> 1 if check(mid) { left = mid } else { right = mid  1 } } return left }