Watch 10 video solutions for Maximum Number of Tasks You Can Assign, a hard level problem involving Array, Binary Search, Greedy. This walkthrough by codestorywithMIK has 12,832 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |