# Maximum Number of Tasks You Can Assign **Difficulty:** HARD [External](https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-tasks-you-can-assign **Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Queue, Monotonic Queue **Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Coupang](https://scaleengineer.com/companies/coupang) --- ## Problem You have `n` tasks and `m` workers. Each task has a strength requirement stored in a **0-indexed** integer array `tasks`, with the `ith` task requiring `tasks[i]` strength to complete. The strength of each worker is stored in a **0-indexed** integer array `workers`, with the `jth` 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 **0-indexed** 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 * 104` * `0 <= pills <= m` * `0 <= tasks[i], workers[j], strength <= 109` # Approaches ## Binary Search with Naive Greedy Check The core idea is to binary search for the maximum number of tasks, `k`, that can be assigned. The range for our binary search will be from `0` to `min(n, m)`. For each `k` we test, we need a helper function, `can_assign(k)`, to check if it's possible to complete `k` tasks. To give ourselves the best chance of success for a given `k`, we should always attempt to complete the `k` easiest tasks using the `k` strongest workers. This is a critical greedy insight. So, we begin by sorting both the `tasks` and `workers` arrays in ascending order. In this first approach, the `can_assign(k)` function is implemented naively. We take the `k` strongest workers (i.e., `workers[m-k]` to `workers[m-1]`) and put them into a list. Then, we iterate through the `k` easiest tasks from hardest to easiest (`tasks[k-1]` down to `tasks[0]`). For each task, we perform a linear scan through our list of available workers to find the weakest one who can complete the task, first without a pill, and if that's not possible, then with a pill. This linear scan for each task leads to a quadratic time complexity for the check function, which is generally too slow. **Time:** O(n log n + m log m + log(min(n, m)) * k^2). Sorting takes `O(n log n + m log m)`. The binary search performs `log(min(n, m))` calls to `can_assign(k)`. `can_assign(k)` takes `O(k^2)` because for each of the `k` tasks, we may scan the list of up to `k` workers. Given the constraints, this is too slow. · **Space:** O(min(n, m)) to store the list of `k` workers within the `can_assign` function. The maximum value of `k` is `min(n, m)`. **Pros:** The binary search approach correctly narrows down the search space for the answer.; The greedy choice of using the easiest tasks and strongest workers is correct and simplifies the problem. **Cons:** The `can_assign(k)` function has a time complexity of O(k^2) due to the linear scan for a suitable worker for each of the k tasks.; This approach is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error. ### Explanation The overall algorithm is structured as a binary search on the answer. The lower bound is `0` and the upper bound is `min(n, m)`. In each step of the binary search, we check if a given number of tasks, `mid`, can be completed. Here's the `can_assign(k)` function in detail: 1. Sort both `tasks` and `workers` arrays initially (can be done once outside the binary search). 2. Create a mutable list (like `ArrayList`) and populate it with the `k` strongest workers: `workers[m-k], ..., workers[m-1]`. 3. Keep a count of the remaining pills. 4. Iterate from `i = k-1` down to `0` (processing tasks from hardest to easiest). 5. For each `task = tasks[i]`, find a suitable worker in the list: - First, search for a worker who can do it without a pill. We iterate through the list to find the index of the weakest worker `w` such that `w >= task`. If multiple such workers exist, we pick the one with the minimum strength to save stronger workers. - If such a worker is found, remove them from the list and continue to the next task. - If not, and if `pills > 0`, search for a worker who can do it with a pill. We find the index of the weakest worker `w` such that `w + strength >= task`. Again, we pick the weakest one possible. - If found, remove them from the list, decrement the pill count, and continue. - If no worker can be found even with a pill, it's impossible to assign `k` tasks. Return `false`. 6. If the loop completes, it means all `k` tasks were assigned. Return `true`. ```java class Solution { public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) { Arrays.sort(tasks); Arrays.sort(workers); int low = 0, high = Math.min(tasks.length, workers.length); int ans = 0; while (low <= high) { int k = low + (high - low) / 2; if (k == 0) { low = k + 1; continue; } if (canAssign(k, tasks, workers, pills, strength)) { ans = k; low = k + 1; } else { high = k - 1; } } return ans; } private boolean canAssign(int k, int[] tasks, int[] workers, int pills, int strength) { List workerList = new ArrayList<>(); for (int i = workers.length - k; i < workers.length; i++) { workerList.add(workers[i]); } for (int i = k - 1; i >= 0; i--) { int task = tasks[i]; boolean assigned = false; // Try to assign without a pill int bestWorkerIndex = -1; for (int j = 0; j < workerList.size(); j++) { if (workerList.get(j) >= task) { if (bestWorkerIndex == -1 || workerList.get(j) < workerList.get(bestWorkerIndex)) { bestWorkerIndex = j; } } } if (bestWorkerIndex != -1) { workerList.remove(bestWorkerIndex); assigned = true; } else if (pills > 0) { // Try to assign with a pill bestWorkerIndex = -1; for (int j = 0; j < workerList.size(); j++) { if (workerList.get(j) + strength >= task) { if (bestWorkerIndex == -1 || workerList.get(j) < workerList.get(bestWorkerIndex)) { bestWorkerIndex = j; } } } if (bestWorkerIndex != -1) { workerList.remove(bestWorkerIndex); pills--; assigned = true; } } if (!assigned) { return false; } } return true; } } ``` ### Algorithm 1. **Binary Search on the Answer**: The number of tasks we can complete is between 0 and `min(n, m)`. Since if we can complete `k` tasks, we can also complete `k-1` tasks, the problem has a monotonic property. This allows us to binary search for the maximum possible value of `k`. 2. **Check Feasibility (`can_assign(k)`)**: For a given `k`, we need to determine if it's possible to assign `k` tasks. - To maximize our chances, we should use the `k` easiest tasks and the `k` strongest workers. Therefore, we first sort both the `tasks` and `workers` arrays. - We will try to assign `tasks[0...k-1]` using workers from `workers[m-k...m-1]`. 3. **Naive Greedy Assignment**: We iterate through the `k` tasks from hardest to easiest (`tasks[k-1]` down to `tasks[0]`). - For each task, we search for a suitable worker from a list containing the `k` strongest workers. - We first try to find the weakest worker who can complete the task without a pill (`worker_strength >= task_strength`). - If no such worker is found, we try to find the weakest worker who can complete it with a pill (`worker_strength + strength >= task_strength`), provided we have pills left. - The search for a worker in the list takes linear time relative to the number of available workers. 4. **Update State**: If a worker is assigned, they are removed from the list of available workers. If a pill is used, the count of pills is decremented. 5. **Result**: If we can assign all `k` tasks, `can_assign(k)` is true, and we try for a larger `k`. Otherwise, it's false, and we try for a smaller `k`. ## Binary Search with Optimized Greedy Check This approach refines the previous one by significantly optimizing the `can_assign(k)` function. The quadratic complexity of the check was due to the linear scan to find a suitable worker. By replacing the simple list of workers with a more powerful data structure, we can reduce the time for this search. A multiset is the perfect tool for this job, as it maintains its elements in sorted order and allows for efficient searching (specifically, finding the smallest element greater than or equal to a value) and deletion. In Java, a `TreeMap` can be used to simulate a multiset, where keys represent worker strengths and values represent the count of workers with that strength. The greedy logic remains the same: for each task (from hardest to easiest), find the least-qualified worker who can complete it. The `TreeMap` allows us to perform this search in `O(log k)` time instead of `O(k)`, dramatically improving the performance of the check function and making the overall solution efficient enough to pass within the time limits. **Time:** O(n log n + m log m + log(min(n, m)) * k * log k). Sorting is `O(n log n + m log m)`. The binary search calls `can_assign` `log(min(n, m))` times. `can_assign(k)` populates a `TreeMap` with `k` elements (`O(k log k)`) and then iterates `k` times, with each iteration performing `O(log k)` operations. The total complexity is well within limits. · **Space:** O(min(n, m)) to store the `k` workers in the `TreeMap`. In the worst case, `k` is `min(n, m)` and all worker strengths are unique. **Pros:** Highly efficient, with a time complexity that should comfortably pass the given constraints.; The logic is robust and correctly models the optimal assignment strategy. **Cons:** The implementation is more complex due to the use of a `TreeMap` to simulate a multiset.; The constant factors for `TreeMap` operations might be higher than for simple array operations, though the overall asymptotic complexity is much better. ### Explanation The binary search framework is identical to the previous approach. The improvement lies entirely within the `can_assign(k)` function. 1. Sort `tasks` and `workers` arrays once. 2. Inside the `can_assign(k)` function: a. Create a `TreeMap` to act as a multiset. Populate it with the `k` strongest workers (`workers[m-k...m-1]`). The keys will be worker strengths, and values will be their frequencies. b. Initialize `pills_left = pills`. c. Iterate from `i = k-1` down to `0` (hardest to easiest task). d. For the current `task = tasks[i]`: i. **Try without a pill**: Find the smallest key in the `TreeMap` that is `>= task`. This can be done with `treeMap.ceilingKey(task)`. ii. If a key is found (i.e., not null), it means we found a worker. We assign this worker. We decrement its count in the map. If the count becomes 0, we remove the key entirely. iii. **Try with a pill**: If no such worker was found, we check if we have pills left. If `pills_left > 0`, we look for a worker who can do the task with a pill. We need a worker `w` such that `w >= task - strength`. We find the smallest key in the `TreeMap` that is `>= task - strength` using `treeMap.ceilingKey(task - strength)`. iv. If this key is found, we assign this worker, use one pill (`pills_left--`), and update the `TreeMap` as before. v. **Failure**: If neither of the above steps results in an assignment, it's impossible to complete this task. We return `false`. 3. If the loop finishes, all `k` tasks have been assigned, so we return `true`. ```java import java.util.Arrays; import java.util.TreeMap; class Solution { public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) { Arrays.sort(tasks); Arrays.sort(workers); int low = 0, high = Math.min(tasks.length, workers.length); int ans = 0; while (low <= high) { int k = low + (high - low) / 2; if (k == 0) { low = k + 1; continue; } if (canAssign(k, tasks, workers, pills, strength)) { ans = k; low = k + 1; } else { high = k - 1; } } return ans; } private boolean canAssign(int k, int[] tasks, int[] workers, int pills, int strength) { TreeMap workerCounts = new TreeMap<>(); for (int i = workers.length - k; i < workers.length; i++) { workerCounts.put(workers[i], workerCounts.getOrDefault(workers[i], 0) + 1); } for (int i = k - 1; i >= 0; i--) { int task = tasks[i]; boolean assigned = false; // Try to assign without a pill Integer workerKey = workerCounts.ceilingKey(task); if (workerKey != null) { // Found a worker who can do it without a pill removeWorker(workerCounts, workerKey); assigned = true; } else if (pills > 0) { // Try to assign with a pill workerKey = workerCounts.ceilingKey(task - strength); if (workerKey != null) { // Found a worker who can do it with a pill pills--; removeWorker(workerCounts, workerKey); assigned = true; } } if (!assigned) { return false; } } return true; } private void removeWorker(TreeMap map, int key) { map.put(key, map.get(key) - 1); if (map.get(key) == 0) { map.remove(key); } } } ``` ### Algorithm 1. **Binary Search on the Answer**: Same as the previous approach, we binary search for the maximum number of tasks `k`. 2. **Optimized Feasibility Check (`can_assign(k)`)**: We again use the `k` easiest tasks and `k` strongest workers after sorting. 3. **Efficient Greedy Assignment**: The key improvement is to use a more efficient data structure to manage the pool of `k` workers. A multiset (simulated using a `TreeMap` in Java) is ideal. It keeps workers sorted and provides logarithmic time complexity for search (`lower_bound`) and removal operations. 4. **Assignment Logic**: We iterate through tasks from hardest to easiest (`tasks[k-1]` down to `tasks[0]`): - For each task `t`, we first query the `TreeMap` for the weakest worker who can do the job without a pill (`w >= t`). This corresponds to finding the smallest key in the map that is greater than or equal to `t`. - If such a worker exists, we assign them, decrement their count in the `TreeMap` (or remove the key if the count becomes zero), and move to the next task. - If not, we must use a pill (if available). We query the `TreeMap` for the weakest worker who can do the job with a pill (`w >= t - strength`). - If this worker is found, we use a pill, update the `TreeMap` and pill count, and proceed. - If at any point a required worker cannot be found, `can_assign(k)` returns `false`. 5. **Result**: If all `k` tasks are successfully assigned, `can_assign(k)` returns `true`. # Solutions ### Java ```java 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 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; } } ``` ### CPP ```cpp class Solution { public: int maxTaskAssign(vector &tasks, vector &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 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; } }; ``` ### Python ```python 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 ```