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.lengthm == workers.length1 <= n, m <= 5 * 1040 <= pills <= m0 <= tasks[i], workers[j], strength <= 109Problem Overview: You receive two arrays: tasks representing required strength and workers representing worker strength. A worker can complete a task if their strength meets the requirement. You also have a limited number of pills that temporarily increase a worker's strength by a fixed amount. The goal is to assign tasks to workers so that the number of completed tasks is maximized.
Approach 1: HashMap + Greedy Feasibility Check (Binary Search) (Time: O(n log n), Space: O(n))
Sort both tasks and workers. Then run a binary search on the number of tasks you attempt to assign. For each candidate value k, try assigning the k easiest tasks to the k strongest workers. A greedy strategy checks from the hardest of these tasks downward. If a worker cannot meet the requirement directly, a pill can be used to temporarily boost their strength. A HashMap or counting structure tracks available boosted assignments and ensures pills are consumed only when necessary. The feasibility check runs in linear time per binary search step, making the full algorithm efficient.
Approach 2: Balanced BST for Ordered Key Access (Binary Search + Greedy) (Time: O(n log n), Space: O(n))
This approach also sorts the arrays and binary searches the number of assignable tasks. During the feasibility check, store the strongest available workers in a balanced binary search tree (such as TreeMap, multiset, or SortedList). Iterate tasks from hardest to easiest among the selected subset. First try to match a worker whose strength already satisfies the task. If none exists, search the structure for the weakest worker who can complete the task after taking a pill. Ordered lookup from the BST makes these operations O(log n). This approach is clean and reliable when implementing greedy matching with dynamic worker availability.
Both solutions rely on the same key insight: the answer is monotonic. If you can assign k tasks, you can assign any number less than k. That property enables efficient binary search. The greedy assignment ensures pills are used only when required and always on the weakest possible worker who can still finish the job.
Recommended for interviews: The binary search + greedy feasibility check using ordered structures is what interviewers typically expect. It demonstrates understanding of monotonic search spaces, efficient task matching, and careful resource usage. Being comfortable with sorted arrays and structures like greedy algorithms, sorting, and ordered containers makes the solution straightforward to reason about.
The first approach involves using a hashmap to store and quickly access data. This is useful when you need to perform quick insertion, deletion, or access operations. You can leverage the hashmap to map keys to their respective values, which provides average O(1) time complexity for these operations.
This C program uses a simple array to implement a hashmap, with each entry as a struct to hold key-value pairs. The hash function is a basic modulus operation to ensure even distribution of keys across the array. Insertion and search operations check the mapped index for the key and perform operations appropriately.
The time complexity for insert and search operations in this hashmap is O(1) on average, assuming good hash distribution. The space complexity is O(n), where n is the number of entries in the hashmap.
The second approach involves using a Balanced Binary Search Tree (BST), such as an AVL tree or Red-Black tree, which organizes keys in sorted order, supporting in-order traversal and ordered operations. This is beneficial when operations requiring order (like finding the smallest/largest element) are needed alongside standard operations.
Implementing a balanced BST in C, such as an AVL tree, involves creating struct nodes with height parameters and implementing rotations for balancing after insertions. Complete implementation details require full rotation and height update mechanisms.
Time complexity for insert, delete, and search in a balanced BST is O(log n), where n is the number of nodes, due to the tree's height maintaining balance. Space complexity is O(n) for n nodes.
Sort the tasks in ascending order of completion time and the workers in ascending order of ability.
Suppose the number of tasks we want to assign is x. We can greedily assign the first x tasks to the x workers with the highest strength. If it is possible to complete x tasks, then it is also possible to complete x-1, x-2, x-3, ..., 1, 0 tasks. Therefore, we can use binary search to find the maximum x such that it is possible to complete x tasks.
We define a function check(x) to determine whether it is possible to complete x tasks.
The implementation of check(x) is as follows:
Iterate through the x workers with the highest strength in ascending order. Let the current worker being processed be j. The current available tasks must satisfy tasks[i] leq workers[j] + strength.
If the smallest required strength task task[i] among the current available tasks is less than or equal to workers[j], then worker j can complete task task[i] without using a pill. Otherwise, the current worker must use a pill. If there are pills remaining, use one pill and complete the task with the highest required strength among the current available tasks. Otherwise, return false.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the number of tasks.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Use a HashMap | The time complexity for insert and search operations in this hashmap is O(1) on average, assuming good hash distribution. The space complexity is O(n), where n is the number of entries in the hashmap. |
| Approach 2: Balanced BST for Ordered Key Access | Time complexity for insert, delete, and search in a balanced BST is O(log n), where n is the number of nodes, due to the tree's height maintaining balance. Space complexity is O(n) for n nodes. |
| Greedy + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap + Greedy Feasibility Check (Binary Search) | O(n log n) | O(n) | Good general solution when using arrays and counting structures to simulate worker assignment. |
| Balanced BST for Ordered Key Access | O(n log n) | O(n) | Preferred when language provides ordered sets/maps for efficient worker lookup. |
Maximum Number of Tasks You Can Assign | Detailed Explanation | Leetcode 2071 | codestorywithMIK • codestorywithMIK • 12,832 views views
Watch 9 more video solutions →Practice Maximum Number of Tasks You Can Assign with our built-in code editor and test cases.
Practice on FleetCode