Maximum Number of Tasks You Can Assign
Problem
Task i needs strength tasks[i] to complete, and worker j has strength workers[j]. You also hold pills magical pills: feeding one to a worker adds strength to that worker, and each worker may take at most one pill. Each worker handles at most one task and each task is done by at most one worker, valid only if the (possibly boosted) worker is at least as strong as the task demands. Return the maximum number of tasks that can be completed.
tasks = [3, 2, 1], workers = [0, 3, 3], pills = 1, strength = 13from collections import deque
def max_task_assign(tasks, workers, pills, strength):
tasks.sort()
workers.sort()
n, m = len(tasks), len(workers)
def can_finish(k):
free, dq, i = pills, deque(), 0
for w in workers[m - k:]: # weakest of the k strongest
while i < k and tasks[i] <= w + strength:
dq.append(i) # within pill reach
i += 1
if not dq:
return False
if tasks[dq[0]] <= w: # easiest task, no pill
dq.popleft()
elif free == 0:
return False
else: # pill on hardest doable
free -= 1
dq.pop()
return True
lo, hi = 0, min(n, m)
while lo < hi: # binary search max k
mid = (lo + hi + 1) // 2
if can_finish(mid):
lo = mid
else:
hi = mid - 1
return lofunction maxTaskAssign(tasks, workers, pills, strength) {
tasks.sort((a, b) => a - b);
workers.sort((a, b) => a - b);
const n = tasks.length, m = workers.length;
const canFinish = (k) => {
let free = pills, i = 0, head = 0;
const dq = []; // deque: head..end
for (const w of workers.slice(m - k)) { // weakest of the k strongest
while (i < k && tasks[i] <= w + strength) dq.push(i++);
if (head === dq.length) return false;
if (tasks[dq[head]] <= w) head++; // easiest task, no pill
else if (free === 0) return false;
else { free--; dq.pop(); } // pill on hardest doable
}
return true;
};
let lo = 0, hi = Math.min(n, m);
while (lo < hi) { // binary search max k
const mid = (lo + hi + 1) >> 1;
if (canFinish(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
int n = tasks.length, m = workers.length;
int lo = 0, hi = Math.min(n, m);
while (lo < hi) { // binary search max k
int mid = (lo + hi + 1) >>> 1;
if (canFinish(tasks, workers, mid, pills, strength)) lo = mid;
else hi = mid - 1;
}
return lo;
}
boolean canFinish(int[] t, int[] w, int k, int free, int strength) {
Deque<Integer> dq = new ArrayDeque<>();
int i = 0, m = w.length;
for (int j = m - k; j < m; j++) { // weakest of the k strongest
while (i < k && t[i] <= w[j] + strength) dq.addLast(i++);
if (dq.isEmpty()) return false;
if (t[dq.peekFirst()] <= w[j]) dq.pollFirst(); // no pill
else if (free == 0) return false;
else { free--; dq.pollLast(); } // pill on hardest doable
}
return true;
}int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end());
int n = tasks.size(), m = workers.size();
auto canFinish = [&](int k) {
int free = pills, i = 0;
deque<int> dq;
for (int j = m - k; j < m; j++) { // weakest of the k strongest
while (i < k && tasks[i] <= workers[j] + strength) dq.push_back(i++);
if (dq.empty()) return false;
if (tasks[dq.front()] <= workers[j]) dq.pop_front(); // no pill
else if (free == 0) return false;
else { free--; dq.pop_back(); } // pill on hardest doable
}
return true;
};
int lo = 0, hi = min(n, m);
while (lo < hi) { // binary search max k
int mid = (lo + hi + 1) / 2;
if (canFinish(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}Explanation
The answer is monotone: if k tasks can be finished, then k − 1 can too (just drop one assignment). So we binary search the largest feasible k. And for a fixed k it never hurts to use the k easiest tasks and the k strongest workers — any other choice can be swapped element-by-element into this one without breaking a valid matching.
The heart of the solution is the feasibility check can_finish(k). It scans the chosen workers weakest first and keeps a deque of candidate tasks: before deciding for worker w, every still-unassigned task with requirement at most w + strength is appended, so the deque holds exactly the tasks this worker could do with a pill, sorted easiest at the front, hardest at the back.
The greedy decision is two-sided. If the front task already fits without a pill (tasks[dq[0]] <= w), take it — the weakest worker mops up the easiest task and every pill is saved. Otherwise this worker needs a pill for any waiting task, so if one remains we spend it on the back of the deque: the hardest task within boosted reach. Clearing the hardest reachable requirement is where a pill buys the most, since easier tasks stay doable for the stronger workers still to come. If the deque is empty or the pills are gone, the check fails.
Default example: tasks = [1,2,3] sorted, workers = [0,3,3], one pill of +1. Trying k = 2, both strength-3 workers grab tasks 1 and 2 pill-free — feasible, so lo = 2. Trying k = 3, worker 0 only reaches task 1 with the pill and spends it, then the two strength-3 workers take tasks 2 and 3 — feasible, so lo = 3 and the answer is 3.
Sorting costs O(n log n + m log m). The binary search runs O(log min(n, m)) checks, and each check does amortized O(1) deque work per worker, i.e. O(min(n, m)) per check. Everything together is O((n + m) log (n + m)) time with O(min(n, m)) extra space for the deque.