2071. Maximum Number of Tasks You Can Assign
Problem Description
In the given problem, you have a certain number of tasks (n
) and workers (m
). Each task has its own strength requirement, and every worker has their own strength level. Their strengths and the strengths required for tasks are given in two separate arrays, tasks
and workers
, respectively.
The objective is to assign tasks to workers. A task can be assigned to a worker only if the worker's strength is greater than or equal to the task's strength requirement. However, there's a twist: you are also provided with pills
magical pills, each of which can increase a single worker's strength by strength
amount. Each worker can receive at most one magical pill.
Your goal is to find the maximum number of tasks that can be completed by appropriately distributing the pills among the workers and assigning the tasks to them.
Intuition
The intuition behind solving this problem involves sorting, greedily matching tasks, and using binary search to find the maximum number of tasks that can be completed.
-
Sorting: First, sort both the
workers
andtasks
arrays. Sorting helps us match the strongest worker to the strongest task they can handle, maximizing the potential number of tasks being completed. -
Binary Search: To find the maximum number of tasks that can be handled, we use binary search. Our search space goes from 0 tasks to the minimum number of tasks or workers (whichever is smaller). The reason for this is that it's not possible to complete more tasks than the total number of workers or tasks available.
-
Greedy Matching with Pills Distribution: For each potential number of tasks (midpoint in binary search), use a greedy approach to assign tasks to workers:
- Work from the strongest (last) worker down to the worker corresponding to the
midpoint
index. - Try to assign the worker to the largest task they can handle without a pill, and if they can't handle any, consider if giving them a pill would allow them to handle the largest remaining task.
- If there are tasks remaining that no worker can handle, even with pills, then the current
midpoint
is not achievable.
- Work from the strongest (last) worker down to the worker corresponding to the
-
Deque Data Structure: A deque (double-ended queue) is used for efficiently popping tasks from the front (if task can be completed without a pill) or from the back (if task requires the use of a pill).
This greedy approach with binary search helps ensure that we are making the most out of the workers and pills available to complete the maximum number of tasks.
Learn more about Greedy, Queue, Binary Search, Sorting and Monotonic Queue patterns.
Solution Approach
The solution is implemented as a class method maxTaskAssign
, containing a nested helper function check
. The primary approach leverages a combination of binary search, greedy matching, and efficient task handling via a deque. Here's a walk-through of the process:
-
Sorting: The
tasks
andworkers
arrays are sorted in ascending order using Python's built-in.sort()
method, because we want to assign the highest possible tasks to our workers based on the order of their strengths, in a greedy fashion. -
Initialization: The variables
n
andm
store the lengths of thetasks
andworkers
arrays, respectively, to determine the boundaries of our search space.left
andright
are used by the binary search algorithm to keep track of the current bounds for the number of tasks we are trying to assign.left
starts at 0 (we know we can at least complete zero tasks), andright
starts as the minimum ofn
orm
because we cannot complete more tasks than we have workers or tasks. -
Binary Search Loop: A while loop is used for binary searching the number of feasibly assignable tasks. In each iteration, it calculates the midpoint
mid
by averagingleft
andright
. Thecheck
function is then called with this midpoint value:-
If
check(mid)
returnsTrue
, it implies that withmid
number of tasks, it's possible to complete them within our constraints, so we shiftleft
tomid
, because we want to try to find a larger number of tasks that might still be possible. -
If
check(mid)
returnsFalse
, it means it's not possible to completemid
number of tasks, so we adjustright
tomid - 1
, hence decreasing our search space.
-
-
The
check
Function: The nestedcheck
function uses a dequeq
for managing the tasks andp
as a pill counter, starting with the total number of pillspills
. It iterates over the stronger workers (from the end ofworkers
array) and checks if tasks can be assigned to them either without a pill or by using one, if available:-
As long as tasks are available that are within the current worker's strength plus potential strength from a pill (
tasks[i] <= workers[j] + strength
), they are added to the deque. -
For every worker, we check if they can complete a task without using a pill. If they can, then we pop the task from the front of the deque (using
q.popleft()
). -
If a worker cannot complete a task without a pill, but no pills are left (
p
is zero), the function returnsFalse
since we cannot assign more tasks. -
If pills are available and a worker cannot do a task without one, we decrement the pill counter
p
by one and remove the hardest task the worker can do with a pill (q.pop()
).
-
-
Final Result: As soon as the binary search is complete, the
left
variable holds the maximum number of tasks that can be completed because it represents the lower bound of the last successful binary search check.
Here, important data structures like the deque and algorithms like binary search and greedy assignment are used together to solve the problem in an efficient manner. This intricately designed approach precisely tailors the pills' distribution and task assignments to maximize output.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example.
Suppose we have the following inputs:
tasks
= [2, 3, 4]workers
= [3, 5, 3]pills
= 2strength
= 1
According to the solution approach, here's what we would do step-by-step:
-
Sorting: We sort both
tasks
andworkers
in ascending order.- Sorted
tasks
= [2, 3, 4] - Sorted
workers
= [3, 3, 5]
- Sorted
-
Initialization: Initialize the search boundaries for binary search.
n
= length oftasks
= 3m
= length ofworkers
= 3left
= 0 (at least no tasks can be completed)right
= min(n
,m
) = 3 (at most all the tasks can be completed)
-
Binary Search Loop: Begin the binary search between 0 and 3.
First Iteration:
left
= 0,right
= 3mid
= (0 + 3) / 2 = 1.5, which is rounded down to 1 since we are working with indices.- Now we check if it is possible to assign 1 task with the given conditions.
- The check passes (because the weakest worker can take the weakest task), so we update
left
tomid + 1
to see if we can assign more.
Second Iteration:
left
= 2,right
= 3mid
= (2 + 3) / 2 = 2.5, which is rounded down to 2.- Now we check if it is possible to assign 2 tasks.
- The check passes as we can give pills to the weaker workers to complete all tasks but the hardest, and thus we update
left
tomid + 1
.
Third Iteration:
left
= 3,right
= 3mid
= (3 + 3) / 2 = 3, so we're checking if we can assign 3 tasks.- We observe that when we assign the strongest worker to the hardest task, the remaining two workers, even with pills, can only handle the two less difficult tasks.
- Thus, the check passes, and
left
should be updated tomid + 1
, but sincemid
is already the upper boundary, the loop ends.
-
The
check
Function: The function would operate as follows for mid=3:- It iterates from the strongest worker to the weakest and checks if they can handle the task directly or with a pill.
- For worker with strength 5, we assign task 4.
- For worker with strength 3, we give a pill (they now have strength 4), to complete task 3.
- For the last worker with strength 3, we give the second pill, now they have strength 4, to complete task 2.
- The pill counting
p
variable which started at 2 would now be 0.
-
Final Result: When our binary search loop is done, the
left
variable accurately reflects the maximum number of tasks that can be assigned: 3 tasks in this example.
In conclusion, by using a careful combination of sorting, binary search, and greedy allocation of the pills, we've effectively maximized the number of tasks completed by the workers.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
6
7 # Define the 'check' function which tries to determine if 'x' tasks can be assigned to workers.
8 def check(x: int) -> bool:
9 task_index = 0
10 workers_under_strength = deque()
11 remaining_pills = pills
12 for worker_index in range(num_workers - x, num_workers):
13 # Assign as many tasks as possible to workers under their available strength plus pills boost
14 while task_index < x and tasks[task_index] <= workers[worker_index] + strength:
15 workers_under_strength.append(tasks[task_index])
16 task_index += 1
17 # If there are no more workers under strength to assign tasks, return False
18 if not workers_under_strength:
19 return False
20 # If the worker can do the task without a pill, pop it from the left
21 if workers_under_strength[0] <= workers[worker_index]:
22 workers_under_strength.popleft()
23 # If no pills are left, it's not possible to assign more tasks
24 elif remaining_pills == 0:
25 return False
26 # Otherwise, use a pill and give the worker the hardest task
27 else:
28 remaining_pills -= 1
29 workers_under_strength.pop()
30 return True
31
32 # Get the number of tasks and workers
33 num_tasks, num_workers = len(tasks), len(workers)
34 # Sort tasks and workers in ascending order
35 tasks.sort()
36 workers.sort()
37
38 # Set the initial binary search range
39 left, right = 0, min(num_tasks, num_workers)
40
41 # Perform a binary search to find the maximum number of tasks that can be assigned
42 while left < right:
43 mid = (left + right + 1) // 2 # Use integer division for Python 3
44 if check(mid):
45 left = mid # If 'mid' tasks can be assigned, try a higher number
46 else:
47 right = mid - 1 # Otherwise, try a lower number
48
49 # The 'left' variable now holds the maximum number of tasks that can be assigned
50 return left
51
1import java.util.Arrays;
2import java.util.ArrayDeque;
3import java.util.Deque;
4
5class Solution {
6 private int[] tasks;
7 private int[] workers;
8 private int strength;
9 private int pills;
10 private int taskCount;
11 private int workerCount;
12
13 // The main function for finding the maximum number of tasks that can be assigned.
14 public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
15 Arrays.sort(tasks);
16 Arrays.sort(workers);
17 this.tasks = tasks;
18 this.workers = workers;
19 this.strength = strength;
20 this.pills = pills;
21 taskCount = tasks.length; // Total number of tasks
22 workerCount = workers.length; // Total number of workers
23
24 // Binary search to find the maximum number of tasks
25 int left = 0, right = Math.min(workerCount, taskCount);
26 while (left < right) {
27 int mid = (left + right + 1) / 2; // Mid-point of the search
28 if (check(mid)) {
29 left = mid; // If mid is possible, search further to the right
30 } else {
31 right = mid - 1; // Otherwise, search to the left
32 }
33 }
34
35 return left; // The maximum number of tasks that can be assigned
36 }
37
38 // A helper function that checks whether x number of tasks can be assigned to the workers.
39 private boolean check(int x) {
40 int taskIdx = 0;
41 Deque<Integer> taskQueue = new ArrayDeque<>();
42 int remainingPills = pills;
43
44 // Iterating over the sorted workers and tasks to determine if the tasks
45 // can be assigned with the constraints of strength and pills.
46 for (int workerIdx = workerCount - x; workerIdx < workerCount; ++workerIdx) {
47 while (taskIdx < x && tasks[taskIdx] <= workers[workerIdx] + strength) {
48 taskQueue.offer(tasks[taskIdx++]); // Add valid tasks to queue
49 }
50 if (taskQueue.isEmpty()) {
51 return false; // No tasks available to assign
52 }
53 if (taskQueue.peekFirst() <= workers[workerIdx]) {
54 taskQueue.pollFirst(); // Assign tasks within current worker capabilities
55 } else if (remainingPills == 0) {
56 return false; // No pills remaining to boost the worker's strength
57 } else {
58 --remainingPills; // Use a pill and assign the most difficult task
59 taskQueue.pollLast();
60 }
61 }
62
63 return true; // Every worker is assigned a task successfully
64 }
65}
66
1class Solution {
2public:
3 int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
4 // Sort tasks and workers so we can use binary search effectively
5 sort(tasks.begin(), tasks.end());
6 sort(workers.begin(), workers.end());
7
8 int taskCount = tasks.size(), workerCount = workers.size();
9 // Initialize binary search boundaries
10 int left = 0, right = min(workerCount, taskCount);
11
12 // Lambda function to check if 'x' is feasible
13 auto canAssignTasks = [&](int x) {
14 int remainingPills = pills;
15 deque<int> availableTasks;
16 int taskIndex = 0;
17 for (int workerIndex = workerCount - x; workerIndex < workerCount; ++workerIndex) {
18 while (taskIndex < x && tasks[taskIndex] <= workers[workerIndex] + strength) {
19 availableTasks.push_back(tasks[taskIndex++]);
20 }
21 // If no tasks can be assigned to the current worker, return false
22 if (availableTasks.empty()) {
23 return false;
24 }
25 // Task can be done without a pill
26 if (availableTasks.front() <= workers[workerIndex]) {
27 availableTasks.pop_front();
28 }
29 // Task requires a pill and we have pills left
30 else if (remainingPills > 0) {
31 --remainingPills;
32 availableTasks.pop_back();
33 }
34 // No pills left and the worker can't do any tasks
35 else {
36 return false;
37 }
38 }
39 return true;
40 };
41
42 // Binary search to find the maximum number of tasks that can be assigned
43 while (left < right) {
44 // Take the upper half of the remaining range
45 int mid = (left + right + 1) / 2;
46 // Check if 'mid' number of tasks can be successfully assigned
47 if (canAssignTasks(mid)) {
48 left = mid;
49 } else {
50 right = mid - 1;
51 }
52 }
53
54 // 'left' will contain the maximum number of tasks that can be assigned
55 return left;
56 }
57};
58
1// Variable declarations according to TypeScript syntax
2let tasks: number[];
3let workers: number[];
4let pills: number;
5let strength: number;
6
7// Function to sort tasks and workers so binary search can be applied effectively
8function sortInputArrays() {
9 tasks.sort((a, b) => a - b);
10 workers.sort((a, b) => a - b);
11}
12
13// Function to check if 'x' tasks can be assigned to workers
14function canAssignTasks(x: number): boolean {
15 let remainingPills = pills;
16 const availableTasks: number[] = [];
17 let taskIndex = 0;
18 const workerStartIndex = workers.length - x;
19 for (let workerIndex = workerStartIndex; workerIndex < workers.length; ++workerIndex) {
20 // Assign as many tasks as possible that workers can do with or without pills
21 while (taskIndex < x && tasks[taskIndex] <= workers[workerIndex] + strength) {
22 availableTasks.push(tasks[taskIndex]);
23 taskIndex++;
24 }
25 // If no tasks can be assigned to the current worker, return false
26 if (availableTasks.length === 0) {
27 return false;
28 }
29 // Task can be done without a pill
30 if (availableTasks[0] <= workers[workerIndex]) {
31 availableTasks.shift();
32 }
33 // Task requires a pill and we have pills left
34 else if (remainingPills > 0) {
35 remainingPills--;
36 availableTasks.pop(); // Use the strongest available task which requires a pill
37 }
38 // No pills left and the worker can't do the task
39 else {
40 return false;
41 }
42 }
43 return true;
44}
45
46// Function to find the maximum number of tasks that can be assigned
47function maxTaskAssign(t: number[], w: number[], p: number, s: number): number {
48 tasks = t;
49 workers = w;
50 pills = p;
51 strength = s;
52
53 // Sort tasks and workers to prepare for binary search
54 sortInputArrays();
55
56 // Initialization for binary search
57 let left = 0;
58 let right = Math.min(workers.length, tasks.length);
59
60 // Binary search to find the maximum number of tasks that can be assigned
61 while (left < right) {
62 // Take the upper half of the remaining range
63 const mid = Math.floor((left + right + 1) / 2);
64 // Check if 'mid' number of tasks can be successfully assigned
65 if (canAssignTasks(mid)) {
66 left = mid;
67 } else {
68 right = mid - 1;
69 }
70 }
71
72 // 'left' will contain the maximum number of tasks that can be assigned
73 return left;
74}
75
Time and Space Complexity
Time Complexity
The given code sorts the tasks
and workers
lists, which has a time complexity of O(n log n)
and O(m log m)
respectively, where n
is the number of tasks and m
is the number of workers.
After sorting, the code performs a binary search to find the maximum number of tasks that can be assigned. The binary search is performed over a range from 0
to min(n, m)
and each iteration of the binary search calls the check
function. Since a binary search has O(log min(n, m))
iterations and the maximum range of binary search is min(n, m):
The check
function itself has a linear scan over the sorted tasks, and a double-ended queue (deque
) to efficiently handle elements at both ends in O(1)
time. For each task in the worst case, one might add to the queue and remove from the queue once, resulting in O(x)
operations, where x
is the number of tasks being checked.
Therefore, the total time complexity of check
is O(x)
, and since it's called in each iteration of the binary search, the overall time complexity of the binary search part is O(x log min(n, m))
.
However, since x
will also be at most min(n, m)
, we can summarize the overall time complexity of the binary search and check
function together as O(min(n, m) log min(n, m))
.
Combining the time complexity of sorting and the binary search gives us the final time complexity of the code:
O(n log n + m log m + min(n, m) log min(n, m))
.
Space Complexity
The additional space used by the code includes the space for the sorted tasks and workers lists and the double-ended queue (deque
).
- The space needed for sorting is
O(n)
for tasks andO(m)
for workers assuming a sorting algorithm such as Timsort (which is used in Python'ssort
function) that requiresO(n)
space. - The
check
function uses adeque
, but since it only contains elements from thetasks
array that are being compared, it would need at mostO(x)
space, wherex
is the number of tasks being checked.
The overall space complexity, therefore, is O(n + m)
taking into account the sorted lists and the temporary space for the deque
.
In summary, the space complexity of the code is O(n + m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Want a Structured Path to Master System Design Too? Don’t Miss This!