Maximum Number of Tasks You Can Assign
Maximum Number of Tasks You Can Assign is a hard binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on k + deque check), runs in O(n log n + m log m) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every k from the top) up.
Problem
There are n tasks and m workers. Task i needs a strength of at least tasks[i], and worker j has strength workers[j]. Each worker can do at most one task and each task needs at most one worker.
You also have pills magic pills. A pill raises one worker’s strength by strength, and each worker can take at most one pill. Decide who gets a pill and who does which task so that as many tasks as possible get done, and return that number.
Examples
Example 1
- Input
tasks = [4, 2, 7], workers = [1, 5, 3], pills = 1, strength = 3- Output
2- Why
- The worker with 5 takes the task needing 4 and the worker with 3 takes the task needing 2. All three cannot be done: 7 needs the 5-worker plus the pill, and then nobody left can manage 4.
Example 2
- Input
tasks = [10, 15, 30], workers = [0, 10, 10, 10, 10], pills = 3, strength = 10- Output
2- Why
- One 10-worker does the 10 task, another takes a pill (10 + 10 = 20) for the 15 task. No one reaches 30 even with a pill.
Example 3
- Input
tasks = [6, 6], workers = [2, 4], pills = 2, strength = 4- Output
2- Why
- Both workers take a pill, reaching 6 and 8, which is enough for both tasks.
Constraints
n == tasks.length,m == workers.length,1 <= n, m <= 5 * 10^40 <= pills <= m0 <= tasks[i], workers[j], strength <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every k from the top) | O(n² log n) | O(n) |
| Optimal (binary search on k + deque check) | O(n log n + m log m) | O(n) |
1Brute force (try every k from the top)
O(n² log n)Up to min(n, m) values of k, each running an O(k log k) multiset check.O(n)The multiset of workers.For a fixed k, it is best to attempt the k easiest tasks with the k strongest workers. A greedy check decides if that works: handle tasks from hardest to easiest; if the strongest remaining worker can do the task unaided, use him; otherwise, if pills are left, give one to the weakest remaining worker who reaches the task with it (keeping stronger workers for later); otherwise fail. Try k = min(n, m), min(n, m) - 1, … and return the first k that passes.
- Sort tasks and workers ascending.
- For k from min(n, m) down to 1: put workers[m - k..m - 1] into a sorted multiset.
- For tasks[k - 1] down to tasks[0]: if max(multiset) >= task, remove the max; else if pills remain, remove the smallest worker >= task - strength (fail if none) and use a pill; else fail.
- Return the first k that does not fail (0 if none).
class Solution {
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
for (int k = Math.min(tasks.length, workers.length); k >= 1; k--)
if (can(tasks, workers, pills, strength, k)) return k;
return 0;
}
private boolean can(int[] tasks, int[] workers, int pills, int strength, int k) {
TreeMap<Integer, Integer> ws = new TreeMap<>();
for (int i = workers.length - k; i < workers.length; i++) ws.merge(workers[i], 1, Integer::sum);
for (int t = k - 1; t >= 0; t--) {
int strongest = ws.lastKey();
int use;
if (strongest >= tasks[t]) use = strongest;
else {
if (pills == 0) return false;
Integer w = ws.ceilingKey(tasks[t] - strength);
if (w == null) return false;
use = w;
pills--;
}
if (ws.merge(use, -1, Integer::sum) == 0) ws.remove(use);
}
return true;
}
}class Solution:
def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
tasks.sort()
workers.sort()
def can(k: int) -> bool:
ws = workers[len(workers) - k:]
p = pills
for t in range(k - 1, -1, -1):
if ws[-1] >= tasks[t]:
ws.pop()
else:
if p == 0:
return False
idx = bisect.bisect_left(ws, tasks[t] - strength)
if idx == len(ws):
return False
ws.pop(idx)
p -= 1
return True
for k in range(min(len(tasks), len(workers)), 0, -1):
if can(k):
return k
return 0class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end());
for (int k = min(tasks.size(), workers.size()); k >= 1; k--)
if (can(tasks, workers, pills, strength, k)) return k;
return 0;
}
private:
bool can(vector<int>& tasks, vector<int>& workers, int pills, int strength, int k) {
multiset<int> ws(workers.end() - k, workers.end());
for (int t = k - 1; t >= 0; t--) {
auto strongest = prev(ws.end());
if (*strongest >= tasks[t]) ws.erase(strongest);
else {
if (pills == 0) return false;
auto it = ws.lower_bound(tasks[t] - strength);
if (it == ws.end()) return false;
ws.erase(it);
pills--;
}
}
return true;
}
};function maxTaskAssign(tasks, workers, pills, strength) {
tasks.sort((a, b) => a - b);
workers.sort((a, b) => a - b);
const lowerBound = (arr, x) => {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
};
const can = (k) => {
const ws = workers.slice(workers.length - k);
let p = pills;
for (let t = k - 1; t >= 0; t--) {
if (ws[ws.length - 1] >= tasks[t]) ws.pop();
else {
if (p === 0) return false;
const idx = lowerBound(ws, tasks[t] - strength);
if (idx === ws.length) return false;
ws.splice(idx, 1);
p--;
}
}
return true;
};
for (let k = Math.min(tasks.length, workers.length); k >= 1; k--)
if (can(k)) return k;
return 0;
}2Optimal (binary search on k + deque check)
O(n log n + m log m)Sorting, plus O(log min(n, m)) checks of O(k) each.O(n)The deque holds at most k task values.Feasibility is monotone in k, so binary search it. The check can also drop the multiset: walk the k chosen workers from weakest to strongest, keeping in a deque the not-yet-done tasks this worker could manage with a pill (tasks are pushed in sorted order while they are <= worker + strength). If the easiest task in the deque is doable without a pill, take it. Otherwise this worker must use a pill and should take the hardest task in the deque, since the easier ones remain open for stronger workers. An empty deque or a missing pill means failure.
- Sort both arrays; lo = 0, hi = min(n, m).
- check(k): ptr = 0, deque empty, p = pills; for each worker w in workers[m - k..m - 1] (ascending): push tasks[ptr++] while ptr < k and tasks[ptr] <= w + strength.
- If the deque is empty, fail. If front <= w, pop front. Else if p == 0 fail, else p-- and pop back.
- Binary search for the largest k with check(k) true.
class Solution {
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
int lo = 0, hi = Math.min(tasks.length, workers.length);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (can(tasks, workers, pills, strength, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private boolean can(int[] tasks, int[] workers, int pills, int strength, int k) {
int[] dq = new int[k];
int head = 0, tail = 0, ptr = 0;
for (int i = workers.length - k; i < workers.length; i++) {
long reach = (long) workers[i] + strength;
while (ptr < k && tasks[ptr] <= reach) dq[tail++] = tasks[ptr++];
if (head == tail) return false;
if (dq[head] <= workers[i]) head++;
else {
if (pills == 0) return false;
pills--;
tail--;
}
}
return true;
}
}class Solution:
def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
tasks.sort()
workers.sort()
m = len(workers)
def can(k: int) -> bool:
dq = deque()
ptr = 0
p = pills
for i in range(m - k, m):
w = workers[i]
reach = w + strength
while ptr < k and tasks[ptr] <= reach:
dq.append(tasks[ptr])
ptr += 1
if not dq:
return False
if dq[0] <= w:
dq.popleft()
else:
if p == 0:
return False
p -= 1
dq.pop()
return True
lo, hi = 0, min(len(tasks), m)
while lo < hi:
mid = (lo + hi + 1) // 2
if can(mid):
lo = mid
else:
hi = mid - 1
return loclass Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end());
int lo = 0, hi = min(tasks.size(), workers.size());
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (can(tasks, workers, pills, strength, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private:
bool can(vector<int>& tasks, vector<int>& workers, int pills, int strength, int k) {
vector<int> dq(k);
int head = 0, tail = 0, ptr = 0, m = workers.size();
for (int i = m - k; i < m; i++) {
long long reach = (long long)workers[i] + strength;
while (ptr < k && tasks[ptr] <= reach) dq[tail++] = tasks[ptr++];
if (head == tail) return false;
if (dq[head] <= workers[i]) head++;
else {
if (pills == 0) return false;
pills--;
tail--;
}
}
return true;
}
};function maxTaskAssign(tasks, workers, pills, strength) {
tasks.sort((a, b) => a - b);
workers.sort((a, b) => a - b);
const m = workers.length;
const can = (k) => {
const dq = new Array(k);
let head = 0, tail = 0, ptr = 0, p = pills;
for (let i = m - k; i < m; i++) {
const reach = workers[i] + strength;
while (ptr < k && tasks[ptr] <= reach) dq[tail++] = tasks[ptr++];
if (head === tail) return false;
if (dq[head] <= workers[i]) head++;
else {
if (p === 0) return false;
p--;
tail--;
}
}
return true;
};
let lo = 0, hi = Math.min(tasks.length, m);
while (lo < hi) {
const mid = (lo + hi + 1) >> 1;
if (can(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}Edge cases to test
- No pills, so it becomes a plain matching of strengths
- strength = 0, so pills are useless
- Every worker is too weak even with a pill: 0
- More workers than tasks, or more tasks than workers
- A tempting greedy that spends a pill on a worker who did not need one
Hints
Hint 1
If k tasks can be completed, which k tasks and which k workers should you pick? Is the answer monotone in k?
Hint 2
It is: if k tasks are possible, so are k - 1. Binary search on k, using the k easiest tasks and the k strongest workers.
Hint 3
To test a k, go through the chosen tasks from hardest to easiest: the strongest remaining worker takes it if he can without a pill; otherwise give a pill to the weakest worker who can then do it.
FAQ
What is the best time complexity for Maximum Number of Tasks You Can Assign?
Optimal (binary search on k + deque check) runs in O(n log n + m log m) time and O(n) extra space. Sorting, plus O(log min(n, m)) checks of O(k) each.
Which pattern does Maximum Number of Tasks You Can Assign use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Maximum Number of Tasks You Can Assign?
Yes. Brute force (try every k from the top) takes O(n² log n) time and O(n) space. For a fixed k, it is best to attempt the k easiest tasks with the k strongest workers.
Which edge cases should I test for Maximum Number of Tasks You Can Assign?
No pills, so it becomes a plain matching of strengths; strength = 0, so pills are useless; Every worker is too weak even with a pill: 0; More workers than tasks, or more tasks than workers; A tempting greedy that spends a pill on a worker who did not need one.