Maximum Number of Tasks You Can Assign

Hard

Walmart

0 views

Topics:

ArraysGreedy AlgorithmsBinary Search

You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the i^th task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the j^th 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.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

Maximum Number of Tasks You Can Assign

Hard

Walmart

0 views

Topics:

ArraysGreedy AlgorithmsBinary Search

You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the i^th task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the j^th 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.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the `tasks` and `workers` array elements? Are they always positive integers?
Can the lengths of the `tasks` and `workers` arrays be different? If so, what should I return if one is significantly shorter than the other?
If no tasks can be assigned according to the difficulty constraints, what should I return?
Are the `tasks` and `workers` arrays guaranteed to be sorted, or do I need to sort them first?
Can the `strength` value be negative or zero?

Brute Force Solution

Approach

The brute force approach to maximizing task assignment involves systematically trying out every possible combination of assigning tasks to workers. We explore all possible subsets of tasks that can be completed, and for each subset, we check if all workers can be assigned to tasks within their capabilities. We continue until we find the largest possible set of tasks that can be assigned.

Here's how the algorithm would work step-by-step:

Start by considering the possibility of assigning no tasks at all.
Then, consider assigning only one task. Try each task individually to see if any worker can do it.
Next, consider assigning two tasks. Try every possible pair of tasks, and for each pair, check if two different workers can handle those tasks.
Continue this process, increasing the number of assigned tasks one by one. For each number of tasks, explore every possible combination of tasks.
For each combination of tasks, determine if there's a matching set of workers capable of performing those tasks, making sure each worker is assigned only one task.
Keep track of the largest number of tasks that can be successfully assigned to workers.
Once you have explored all possible combinations of tasks, the largest number of tasks you recorded is the maximum number of tasks that can be assigned.

Code Implementation

def max_tasks_brute_force(tasks, workers):
    number_of_tasks = len(tasks)
    number_of_workers = len(workers)
    maximum_assigned_tasks = 0

    for number_of_tasks_to_assign in range(number_of_tasks + 1):
        # Iterate through all possible combinations
        from itertools import combinations
        for task_combination in combinations(range(number_of_tasks), number_of_tasks_to_assign):
            
            can_assign_tasks = True
            worker_assignment = [-1] * number_of_tasks_to_assign

            # Check if each task can be assigned to a worker
            def find_assignment(task_index_to_assign, assigned_workers):
                nonlocal can_assign_tasks
                if task_index_to_assign == number_of_tasks_to_assign:
                    return True

                task_index = task_combination[task_index_to_assign]

                for worker_index in range(number_of_workers):
                    # Check if the worker is capable and is not yet assigned.
                    if tasks[task_index] <= workers[worker_index] and worker_index not in assigned_workers:
                        worker_assignment[task_index_to_assign] = worker_index
                        
                        if find_assignment(task_index_to_assign + 1, assigned_workers + [worker_index]):
                            return True
                        # Backtrack if the current worker assignment doesn't lead to a solution.
                        worker_assignment[task_index_to_assign] = -1

                return False

            #Begin assigning tasks
            if number_of_tasks_to_assign <= number_of_workers:
                # Only attempt assignment if enough workers exist
                if not find_assignment(0, []):
                    can_assign_tasks = False

            else:
                can_assign_tasks = False

            if can_assign_tasks:
                #Update the max assigned task count
                maximum_assigned_tasks = max(maximum_assigned_tasks, number_of_tasks_to_assign)

    return maximum_assigned_tasks

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(n+m) * m!) – The algorithm iterates through all possible subsets of tasks, where n is the number of tasks. This results in 2^n possible task combinations. For each of these combinations, it attempts to find a valid assignment of tasks to workers, where m is the number of workers. Finding an assignment involves checking all possible permutations of workers for the selected tasks which is m! in the worst case where n=m. Additionally we iterate through workers capabilities so we would multiply m to 2^n * m!. Therefore, the overall time complexity is approximately O(2^(n) * m! * m). The 2^n component dominates, but we must consider iterating over workers which leads to a worst case time complexity approximation of O(2^(n+m) * m!).

Space Complexity

O(1) – The described brute force approach, as outlined, primarily utilizes iterative exploration. While combinations of tasks are considered, the plain English description doesn't explicitly mention auxiliary data structures growing with the number of tasks or workers. There's no indication of storing intermediate combinations in a manner that significantly impacts memory. Therefore, the space complexity remains relatively constant, independent of the number of tasks or workers, suggesting O(1) auxiliary space.

Optimal Solution

Approach

The goal is to maximize the number of assigned tasks by efficiently matching workers to tasks. The key idea is to sort both workers and tasks and then greedily assign the weakest worker to the easiest task to determine how many pairings are possible. We use a checking process that attempts to assign pairings and narrows down the possible assignment amounts.

Here's how the algorithm would work step-by-step:

First, sort both the list of worker abilities and the list of task difficulties from easiest to hardest.
Use a checking process: start with a guess for the number of tasks you think you can assign (potentially the total number of workers or tasks, whichever is smaller).
Check if it's possible to assign that many tasks. To do this, assign each of the weakest workers to each of the easiest tasks within the chosen range. A worker can only be assigned if they have the ability to complete their assigned task.
If every worker can complete their assigned task within the range then that means it is possible to assign that many tasks.
If not every worker can complete their assigned task, reduce the assumed number of tasks and repeat the checking process.
Repeat until you have found the largest possible number of tasks that can be successfully assigned. The sorted order ensures you're always trying the easiest tasks first, making this process efficient.

Code Implementation

def maximum_number_of_tasks_you_can_assign(workers, tasks):
    workers.sort()
    tasks.sort()

    left_bound = 0
    right_bound = min(len(workers), len(tasks))
    max_tasks = 0

    while left_bound <= right_bound:
        midpoint = (left_bound + right_bound) // 2

        if is_possible(workers, tasks, midpoint):
            # Increase left to find a higher possible number.
            max_tasks = midpoint
            left_bound = midpoint + 1

        else:
            right_bound = midpoint - 1

    return max_tasks

def is_possible(workers, tasks, number_of_assignments):
    worker_index = 0
    task_index = number_of_assignments - 1

    # Check if we can assign tasks with the given number of assignments.
    while worker_index < len(workers) and task_index >= 0:
        if workers[worker_index] >= tasks[task_index]:
            worker_index += 1
            task_index -= 1
        else:
            task_index = -1 #early exit
            break

    # If task_index is less than 0, all tasks were assigned successfully.
    if task_index < 0:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting both the worker abilities and task difficulties arrays, each of size n (assuming the number of workers and tasks is approximately the same). Sorting using efficient algorithms like merge sort or quicksort takes O(n log n) time. The checking process, potentially implemented using a binary search-like approach to find the maximum assignable tasks, performs a feasibility check. The feasibility check iterates through the selected workers and tasks to see if an assignment is possible which contributes O(n) within the binary search structure. Considering binary search's logarithmic nature on the assignable task counts this makes the iterative checking process O(n log n) in the worst case. Since sorting and the checking process each take O(n log n) time, the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm primarily utilizes sorting, but the provided plain English description does not explicitly specify the use of any auxiliary data structures for sorting (e.g., a temporary array for merge sort). It mentions a checking process involving assigning tasks, but this only involves comparing worker abilities with task difficulties within a chosen range, using existing worker and task arrays and does not mention any extra storage for this assignment. Therefore, it appears that only a few variables are used during the checking process which require constant space. Consequently, the auxiliary space remains constant irrespective of the input size (number of workers and tasks).

Edge Cases

Case	How to Handle
tasks array is null or empty	Return 0 immediately as no tasks can be assigned.
workers array is null or empty	Return 0 immediately as no tasks can be assigned.
pills is zero	Simulate without pills, effectively only allowing tasks a worker can complete without a pill.
strength is zero, tasks are all non-zero	Return 0 because the pill's strength is useless.
Maximum array size for tasks/workers (scalability)	The solution should scale efficiently, potentially using a linearithmic (N log N) sorting algorithm, ensuring it handles large inputs without exceeding time limits.
tasks array contains only very large values (close to MAX_INT)	Ensure no integer overflow occurs during strength calculations or binary search comparisons by using appropriate data types.
tasks and workers are perfectly matched (tasks[i] == workers[i] for all i)	The algorithm should return the size of the arrays if all are assigned.
tasks are significantly harder than workers' base ability (require pills)	Handle cases where the optimal assignment requires strategically using pills to maximize the number of completed tasks.