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.
Input: tasks =[3̲,2̲,1̲], workers =[0̲,3̲,3̲], pills =1, strength =1Output: 3Explanation:
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:
1
2
3
4
5
6
Input: tasks =[5̲,4], workers =[0̲,0,0], pills =1, strength =5Output: 1Explanation:
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:
1
2
3
4
5
6
7
8
Input: tasks =[10̲,15̲,30], workers =[0̲,1̲0̲,10,10,10], pills =3, strength =10Output: 2Explanation:
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.
The approach stems from using binary search combined with a greedy algorithm to determine the maximum number of tasks that can be completed. Here’s the breakdown:
Sorting:
Sort both tasks and workers so that tasks are matched optimally (easiest task to weakest worker).
Sorting ensures easier pairing, both with and without pills.
Binary Search:
Define the search range as [0, min(n, m)], where n is the number of tasks and m is the number of workers.
For each mid value (number of tasks being tested):
Check if it’s feasible to assign mid tasks using the workers and pills available.
Adjust the bounds (l, h) based on feasibility.
Feasibility Check (canComplete):
Use a deque (double-ended queue) to manage workers capable of being boosted with pills (those within range of task difficulty).
Assign tasks starting from the hardest task downwards:
If a worker (from the end of deque) can finish the task without a pill, assign the worker directly.
Else if pills are feasible, assign the weakest worker in the deque and use a pill.
Break early if no feasible worker exists for a task.
Optimisation:
Always prioritise workers who do not need pills first and conserve pills for tasks that cannot otherwise be completed.
classSolution {
publicintmaxTaskAssign(
int[] tasks,
int[] workers,
int pills,
int strength
) {
Arrays.sort(tasks);
Arrays.sort(workers);
int l = 0, h = Math.min(tasks.length, workers.length), ans = 0;
while (l <= h) {
int mid = (l + h) / 2;
if (canComplete(mid, tasks, workers, pills, strength)) {
ans = mid; // Update the result if feasible l = mid + 1; // Try higher task count } else {
h = mid - 1; // Try lower task count }
}
return ans;
}
privatebooleancanComplete(
int count,
int[] tasks,
int[] workers,
int pills,
int strength
) {
Deque<Integer> dq =new ArrayDeque<>();
int j = workers.length- 1;
// Iterate through tasks from the hardest (for the current subset of tasks)for (int i = count - 1; i >= 0; i--) {
// Add workers to deque that can be boosted with pills to complete taskswhile (
j >= workers.length- count && workers[j]+ strength >= tasks[i] ) {
dq.addFirst(workers[j]);
j--;
}
if (dq.isEmpty()) {
returnfalse; // No worker can handle the current task } elseif (dq.peekLast() >= tasks[i]) {
dq.pollLast(); // Assign the strongest worker available without a pill } else {
if (pills == 0) {
returnfalse; // No pills left to boost the worker's strength }
dq.pollFirst(); // Use pill on weakest worker pills--;
}
}
returntrue; // All tasks can be handled }
}
classSolution:
defmaxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
# Sort tasks and workers for greedy pairing tasks.sort()
workers.sort()
# Binary search to find maximum number of tasks l, h, ans =0, min(len(tasks), len(workers)), 0while l <= h:
mid = (l + h) //2if self.canComplete(mid, tasks, workers, pills, strength):
ans = mid # Update result l = mid +1# Try higher task countelse:
h = mid -1# Try lower task countreturn ans
defcanComplete(self, count: int, tasks: List[int], workers: List[int], pills: int, strength: int) -> bool:
# Double-ended queue to store workers useful for boosting dq = deque()
j = len(workers) -1# Iterate from hardest task down to easiestfor i in range(count -1, -1, -1):
# Push workers who can be boosted to the dequewhile j >= len(workers) - count and workers[j] + strength >= tasks[i]:
dq.appendleft(workers[j])
j -=1# No worker left for current taskifnot dq:
returnFalse# Assign strongest worker without a pillelif dq[-1] >= tasks[i]:
dq.pop()
# Use a pill and assign weakest workerelse:
if pills ==0:
returnFalse# No pills left dq.popleft()
pills -=1returnTrue# All tasks can be handled