Maximum Number of Tasks You Can Assign — Problem & Solution
Maximum Number of Tasks You Can Assign solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Number of Tasks You Can Assign is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Databricks interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy, Binary Search, Queue
- Asked at: Amazon, Google, Databricks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Task i needs strength tasks[i]; worker j has strength workers[j]. Each worker takes at most one task, and can take task i only if their strength is at least tasks[i].
You also have pills magical pills; giving one to a worker raises their strength by strength permanently. Each worker takes at most one pill. Return the maximum number of tasks that can be assigned.
Example 1
Input: tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
Output: 3
Explanation: Pill the strength-0 worker to handle task 1.
Example 2
Input: tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
Output: 1
Example 3
Input: tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
Output: 2
Constraints
1 <= tasks.length, workers.length <= 10000 <= pills <= workers.length0 <= tasks[i], workers[j], strength <= 1000000000
Hints for Maximum Number of Tasks You Can Assign
Hint 1
If
ktasks can be assigned, so cank - 1— binary searchk.Hint 2
For a given
k, always use thekeasiest tasks and thekstrongest workers.Hint 3
Assign the hardest of those tasks first; use a pill only when the strongest free worker cannot manage it, and then pick the weakest worker who can with a pill.
How to solve Maximum Number of Tasks You Can Assign
Binary search the number of tasks. For a fixed k, the choice of which tasks and workers to use is forced — the easiest tasks and the strongest workers — and then a greedy from the hardest task downwards, spending pills as late and as cheaply as possible, decides feasibility.
Approach
- Sort both arrays. For a candidate
k, taketasks[0 … k-1]and the topkworkers. - Walk the chosen tasks from hardest to easiest. If the strongest free worker already qualifies, use them.
- Otherwise spend a pill on the weakest free worker who qualifies with it — found by binary search — so stronger workers stay for harder tasks.
- If no worker qualifies even with a pill, or pills run out,
kis infeasible.
Why it works
Using the easiest tasks and strongest workers is an exchange argument: swapping in an easier task or a stronger worker never breaks a valid assignment. Within that, handling the hardest task first is forced because only the strongest workers can do it, and when a pill is needed the weakest qualifying worker is the right choice — spending the pill on anyone stronger wastes capacity that a harder task might have needed.
Complexity
- Time —
O(n log n + n² log n) at these limits - Space —
O(n)
Pitfalls
- Assigning the easiest task first, or pilling the strongest worker, both give wrong answers.
- The strongest free worker must be checked before reaching for a pill, or pills get wasted.
workers[j] + strengthreaches2 · 10^9— the comparison needs 64-bit in languages whereintis 32-bit.
Reference solution
Python
from typing import List
def maxTaskAssign(tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
t = sorted(tasks)
w = sorted(workers)
def check(k: int) -> bool:
left = pills
avail = w[len(w) - k:]
for i in range(k - 1, -1, -1):
need = t[i]
if avail and avail[-1] >= need:
avail.pop()
continue
if left == 0:
return False
lo, hi = 0, len(avail)
while lo < hi:
mid = (lo + hi) // 2
if avail[mid] + strength >= need:
hi = mid
else:
lo = mid + 1
if lo == len(avail):
return False
avail.pop(lo)
left -= 1
return True
lo, hi, ans = 0, min(len(t), len(w)), 0
while lo <= hi:
mid = (lo + hi) // 2
if mid == 0 or check(mid):
ans = mid
lo = mid + 1
else:
hi = mid - 1
return ansJava
private static boolean canAssign(int[] t, int[] w, int pills, int strength, int k) {
int left = pills;
List<Integer> avail = new ArrayList<>();
for (int i = w.length - k; i < w.length; i++) avail.add(w[i]);
for (int i = k - 1; i >= 0; i--) {
int need = t[i];
if (!avail.isEmpty() && avail.get(avail.size() - 1) >= need) {
avail.remove(avail.size() - 1);
continue;
}
if (left == 0) return false;
int lo = 0, hi = avail.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if ((long) avail.get(mid) + strength >= need) hi = mid; else lo = mid + 1;
}
if (lo == avail.size()) return false;
avail.remove(lo);
left--;
}
return true;
}
public static int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
int[] t = tasks.clone();
int[] w = workers.clone();
Arrays.sort(t);
Arrays.sort(w);
int lo = 0, hi = Math.min(t.length, w.length), ans = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid == 0 || canAssign(t, w, pills, strength, mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}C++
static bool canAssign(vector<int>& t, vector<int>& w, int pills, int strength, int k) {
int left = pills;
vector<int> avail(w.end() - k, w.end());
for (int i = k - 1; i >= 0; i--) {
int need = t[i];
if (!avail.empty() && avail.back() >= need) {
avail.pop_back();
continue;
}
if (left == 0) return false;
int lo = 0, hi = (int) avail.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((long long) avail[mid] + strength >= need) hi = mid; else lo = mid + 1;
}
if (lo == (int) avail.size()) return false;
avail.erase(avail.begin() + lo);
left--;
}
return true;
}
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
vector<int> t = tasks, w = workers;
sort(t.begin(), t.end());
sort(w.begin(), w.end());
int lo = 0, hi = min((int) t.size(), (int) w.size()), ans = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid == 0 || canAssign(t, w, pills, strength, mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}JavaScript
var maxTaskAssign = function(tasks, workers, pills, strength) {
var t = tasks.slice().sort(function(a, b) { return a - b; });
var w = workers.slice().sort(function(a, b) { return a - b; });
var check = function(k) {
var left = pills;
var avail = w.slice(w.length - k);
for (var i = k - 1; i >= 0; i--) {
var need = t[i];
if (avail.length > 0 && avail[avail.length - 1] >= need) { avail.pop(); continue; }
if (left === 0) return false;
var lo = 0, hi = avail.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (avail[mid] + strength >= need) hi = mid; else lo = mid + 1;
}
if (lo === avail.length) return false;
avail.splice(lo, 1);
left--;
}
return true;
};
var low = 0, high = Math.min(t.length, w.length), ans = 0;
while (low <= high) {
var m = Math.floor((low + high) / 2);
if (m === 0 || check(m)) { ans = m; low = m + 1; } else high = m - 1;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms