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.

  1. Sorting: First, sort both the workers and tasks arrays. Sorting helps us match the strongest worker to the strongest task they can handle, maximizing the potential number of tasks being completed.

  2. 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.

  3. 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.
  4. 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.

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:

  1. Sorting: The tasks and workers 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.

  2. Initialization: The variables n and m store the lengths of the tasks and workers arrays, respectively, to determine the boundaries of our search space. left and right 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), and right starts as the minimum of n or m because we cannot complete more tasks than we have workers or tasks.

  3. 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 averaging left and right. The check function is then called with this midpoint value:

    • If check(mid) returns True, it implies that with mid number of tasks, it's possible to complete them within our constraints, so we shift left to mid, because we want to try to find a larger number of tasks that might still be possible.

    • If check(mid) returns False, it means it's not possible to complete mid number of tasks, so we adjust right to mid - 1, hence decreasing our search space.

  4. The check Function: The nested check function uses a deque q for managing the tasks and p as a pill counter, starting with the total number of pills pills. It iterates over the stronger workers (from the end of workers 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 returns False 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()).

  5. 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.

💪
Level Up Your
Algo Skills

Example 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 = 2
  • strength = 1

According to the solution approach, here's what we would do step-by-step:

  1. Sorting: We sort both tasks and workers in ascending order.

    • Sorted tasks = [2, 3, 4]
    • Sorted workers = [3, 3, 5]
  2. Initialization: Initialize the search boundaries for binary search.

    • n = length of tasks = 3
    • m = length of workers = 3
    • left = 0 (at least no tasks can be completed)
    • right = min(n, m) = 3 (at most all the tasks can be completed)
  3. Binary Search Loop: Begin the binary search between 0 and 3.

    First Iteration:

    • left = 0, right = 3
    • mid = (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 to mid + 1 to see if we can assign more.

    Second Iteration:

    • left = 2, right = 3
    • mid = (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 to mid + 1.

    Third Iteration:

    • left = 3, right = 3
    • mid = (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 to mid + 1, but since mid is already the upper boundary, the loop ends.
  4. 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.
  5. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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 and O(m) for workers assuming a sorting algorithm such as Timsort (which is used in Python's sort function) that requires O(n) space.
  • The check function uses a deque, but since it only contains elements from the tasks array that are being compared, it would need at most O(x) space, where x 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).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫