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.

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}

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