Maximum Number of Tasks You Can Assign

Hard

#1886Time: 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)`.3 companies

Patterns

Two Pointers Greedy

Algorithms

Binary Search Sorting

Data structures

Array Queue Monotonic Queue

Companies

IBM Walmart Labs Coupang

Prompt

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 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 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 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

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.
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].
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.
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.
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.

Walkthrough

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:

Sort both tasks and workers arrays initially (can be done once outside the binary search).
Create a mutable list (like ArrayList) and populate it with the k strongest workers: workers[m-k], ..., workers[m-1].
Keep a count of the remaining pills.
Iterate from i = k-1 down to 0 (processing tasks from hardest to easiest).
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.
If the loop completes, it means all k tasks were assigned. Return true.

1class Solution {2    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {3        Arrays.sort(tasks);4        Arrays.sort(workers);5        int low = 0, high = Math.min(tasks.length, workers.length);6        int ans = 0;7        while (low <= high) {8            int k = low + (high - low) / 2;9            if (k == 0) {10                low = k + 1;11                continue;12            }13            if (canAssign(k, tasks, workers, pills, strength)) {14                ans = k;15                low = k + 1;16            } else {17                high = k - 1;18            }19        }20        return ans;21    }22 23    private boolean canAssign(int k, int[] tasks, int[] workers, int pills, int strength) {24        List<Integer> workerList = new ArrayList<>();25        for (int i = workers.length - k; i < workers.length; i++) {26            workerList.add(workers[i]);27        }28 29        for (int i = k - 1; i >= 0; i--) {30            int task = tasks[i];31            boolean assigned = false;32 33            // Try to assign without a pill34            int bestWorkerIndex = -1;35            for (int j = 0; j < workerList.size(); j++) {36                if (workerList.get(j) >= task) {37                    if (bestWorkerIndex == -1 || workerList.get(j) < workerList.get(bestWorkerIndex)) {38                        bestWorkerIndex = j;39                    }40                }41            }42            if (bestWorkerIndex != -1) {43                workerList.remove(bestWorkerIndex);44                assigned = true;45            } else if (pills > 0) {46                // Try to assign with a pill47                bestWorkerIndex = -1;48                for (int j = 0; j < workerList.size(); j++) {49                    if (workerList.get(j) + strength >= task) {50                        if (bestWorkerIndex == -1 || workerList.get(j) < workerList.get(bestWorkerIndex)) {51                            bestWorkerIndex = j;52                        }53                    }54                }55                if (bestWorkerIndex != -1) {56                    workerList.remove(bestWorkerIndex);57                    pills--;58                    assigned = true;59                }60            }61 62            if (!assigned) {63                return false;64            }65        }66        return true;67    }68}

Complexity

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)`.

Trade-offs

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.

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<Integer, Integer> 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.

Algorithm

Binary Search on the Answer: Same as the previous approach, we binary search for the maximum number of tasks k.
Optimized Feasibility Check (can_assign(k)): We again use the k easiest tasks and k strongest workers after sorting.
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.
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.
Result: If all k tasks are successfully assigned, can_assign(k) returns true.

Walkthrough

The binary search framework is identical to the previous approach. The improvement lies entirely within the can_assign(k) function.

Sort tasks and workers arrays once.
Inside the can_assign(k) function: a. Create a TreeMap<Integer, Integer> 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.
If the loop finishes, all k tasks have been assigned, so we return true.

1import java.util.Arrays;2import java.util.TreeMap;3 4class Solution {5    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {6        Arrays.sort(tasks);7        Arrays.sort(workers);8        int low = 0, high = Math.min(tasks.length, workers.length);9        int ans = 0;10        while (low <= high) {11            int k = low + (high - low) / 2;12            if (k == 0) {13                low = k + 1;14                continue;15            }16            if (canAssign(k, tasks, workers, pills, strength)) {17                ans = k;18                low = k + 1;19            } else {20                high = k - 1;21            }22        }23        return ans;24    }25 26    private boolean canAssign(int k, int[] tasks, int[] workers, int pills, int strength) {27        TreeMap<Integer, Integer> workerCounts = new TreeMap<>();28        for (int i = workers.length - k; i < workers.length; i++) {29            workerCounts.put(workers[i], workerCounts.getOrDefault(workers[i], 0) + 1);30        }31 32        for (int i = k - 1; i >= 0; i--) {33            int task = tasks[i];34            boolean assigned = false;35 36            // Try to assign without a pill37            Integer workerKey = workerCounts.ceilingKey(task);38            if (workerKey != null) {39                // Found a worker who can do it without a pill40                removeWorker(workerCounts, workerKey);41                assigned = true;42            } else if (pills > 0) {43                // Try to assign with a pill44                workerKey = workerCounts.ceilingKey(task - strength);45                if (workerKey != null) {46                    // Found a worker who can do it with a pill47                    pills--;48                    removeWorker(workerCounts, workerKey);49                    assigned = true;50                }51            }52 53            if (!assigned) {54                return false;55            }56        }57        return true;58    }59 60    private void removeWorker(TreeMap<Integer, Integer> map, int key) {61        map.put(key, map.get(key) - 1);62        if (map.get(key) == 0) {63            map.remove(key);64        }65    }66}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int[] tasks;4private5  int[] workers;6private7  int strength;8private9  int pills;10private11  int m;12private13  int n;14public15  int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {16    Arrays.sort(tasks);17    Arrays.sort(workers);18    this.tasks = tasks;19    this.workers = workers;20    this.strength = strength;21    this.pills = pills;22    n = tasks.length;23    m = workers.length;24    int left = 0, right = Math.min(m, n);25    while (left < right) {26      int mid = (left + right + 1) >> 1;27      if (check(mid)) {28        left = mid;29      } else {30        right = mid - 1;31      }32    }33    return left;34  }35private36  boolean check(int x) {37    int i = 0;38    Deque<Integer> q = new ArrayDeque<>();39    int p = pills;40    for (int j = m - x; j < m; ++j) {41      while (i < x && tasks[i] <= workers[j] + strength) {42        q.offer(tasks[i++]);43      }44      if (q.isEmpty()) {45        return false;46      }47      if (q.peekFirst() <= workers[j]) {48        q.pollFirst();49      } else if (p == 0) {50        return false;51      } else {52        --p;53        q.pollLast();54      }55    }56    return true;57  }58}

1class Solution {2public:3  int maxTaskAssign(vector<int> &tasks, vector<int> &workers, int pills,4                    int strength) {5    sort(tasks.begin(), tasks.end());6    sort(workers.begin(), workers.end());7    int n = tasks.size(), m = workers.size();8    int left = 0, right = min(m, n);9    auto check = [&](int x) {10      int p = pills;11      deque<int> q;12      int i = 0;13      for (int j = m - x; j < m; ++j) {14        while (i < x && tasks[i] <= workers[j] + strength) {15          q.push_back(tasks[i++]);16        }17        if (q.empty()) {18          return false;19        }20        if (q.front() <= workers[j]) {21          q.pop_front();22        } else if (p == 0) {23          return false;24        } else {25          --p;26          q.pop_back();27        }28      }29      return true;30    };31    while (left < right) {32      int mid = (left + right + 1) >> 1;33      if (check(mid)) {34        left = mid;35      } else {36        right = mid - 1;37      }38    }39    return left;40  }41};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem