2071. Maximum Number of Tasks You Can Assign
Description
You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the ith task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the jth 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.lengthm == workers.length1 <= n, m <= 5 * 1040 <= pills <= m0 <= tasks[i], workers[j], strength <= 109
Solutions
Solution 1: Greedy + Binary Search
Sort the tasks in ascending order of completion time and the workers in ascending order of ability.
Suppose the number of tasks we want to assign is $x$. We can greedily assign the first $x$ tasks to the $x$ workers with the highest strength. If it is possible to complete $x$ tasks, then it is also possible to complete $x-1$, $x-2$, $x-3$, ..., $1$, $0$ tasks. Therefore, we can use binary search to find the maximum $x$ such that it is possible to complete $x$ tasks.
We define a function $check(x)$ to determine whether it is possible to complete $x$ tasks.
The implementation of $check(x)$ is as follows:
Iterate through the $x$ workers with the highest strength in ascending order. Let the current worker being processed be $j$. The current available tasks must satisfy $tasks[i] \leq workers[j] + strength$.
If the smallest required strength task $task[i]$ among the current available tasks is less than or equal to $workers[j]$, then worker $j$ can complete task $task[i]$ without using a pill. Otherwise, the current worker must use a pill. If there are pills remaining, use one pill and complete the task with the highest required strength among the current available tasks. Otherwise, return false.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the number of tasks.
Python3
class Solution:
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
Java
class Solution {
private int[] tasks;
private int[] workers;
private int strength;
private int pills;
private int m;
private int n;
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
this.tasks = tasks;
this.workers = workers;
this.strength = strength;
this.pills = pills;
n = tasks.length;
m = workers.length;
int left = 0, right = Math.min(m, n);
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private boolean check(int x) {
int i = 0;
Deque<Integer> q = new ArrayDeque<>();
int p = pills;
for (int j = m - x; j < m; ++j) {
while (i < x && tasks[i] <= workers[j] + strength) {
q.offer(tasks[i++]);
}
if (q.isEmpty()) {
return false;
}
if (q.peekFirst() <= workers[j]) {
q.pollFirst();
} else if (p == 0) {
return false;
} else {
--p;
q.pollLast();
}
}
return true;
}
}
C++
class 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 n = tasks.size(), m = workers.size();
int left = 0, right = min(m, n);
auto check = [&](int x) {
int p = pills;
deque<int> q;
int i = 0;
for (int j = m - x; j < m; ++j) {
while (i < x && tasks[i] <= workers[j] + strength) {
q.push_back(tasks[i++]);
}
if (q.empty()) {
return false;
}
if (q.front() <= workers[j]) {
q.pop_front();
} else if (p == 0) {
return false;
} else {
--p;
q.pop_back();
}
}
return true;
};
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
};
Go
func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
sort.Ints(tasks)
sort.Ints(workers)
n, m := len(tasks), len(workers)
left, right := 0, min(m, n)
check := func(x int) bool {
p := pills
q := []int{}
i := 0
for j := m - x; j < m; j++ {
for i < x && tasks[i] <= workers[j]+strength {
q = append(q, tasks[i])
i++
}
if len(q) == 0 {
return false
}
if q[0] <= workers[j] {
q = q[1:]
} else if p == 0 {
return false
} else {
p--
q = q[:len(q)-1]
}
}
return true
}
for left < right {
mid := (left + right + 1) >> 1
if check(mid) {
left = mid
} else {
right = mid - 1
}
}
return left
}
TypeScript
function maxTaskAssign(
tasks: number[],
workers: number[],
pills: number,
strength: number,
): number {
tasks.sort((a, b) => a - b);
workers.sort((a, b) => a - b);
const n = tasks.length;
const m = workers.length;
const check = (x: number): boolean => {
const dq = new Array<number>(x);
let head = 0;
let tail = 0;
const empty = () => head === tail;
const pushBack = (val: number) => {
dq[tail++] = val;
};
const popFront = () => {
head++;
};
const popBack = () => {
tail--;
};
const front = () => dq[head];
let i = 0;
let p = pills;
for (let j = m - x; j < m; j++) {
while (i < x && tasks[i] <= workers[j] + strength) {
pushBack(tasks[i]);
i++;
}
if (empty()) return false;
if (front() <= workers[j]) {
popFront();
} else {
if (p === 0) return false;
p--;
popBack();
}
}
return true;
};
let [left, right] = [0, Math.min(n, m)];
while (left < right) {
const mid = (left + right + 1) >> 1;
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}