Maximum Number of Tasks Assignment Problem

Problem Statement

We have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array of tasks, with the ith task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array of 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.

Examples:

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 1 (0 + 5 >= 5)

In this example, there is only one task, and worker 0's strength is sufficient to complete it.

Java Approach Using Greedy Algorithm and Binary Search

Output:

Code Explanation:

• The code implements a task assignment algorithm that optimizes worker task completion. The maxTaskAssign method uses binary search to find the maximum number of tasks that can be completed, given the constraints.
• The canCompleteTasks helper method simulates the assignment process, using a deque to manage tasks and pills for completing tasks beyond workers' strength.
• The algorithm iterates through workers, assigning tasks based on their strengths. The binary search optimally selects the starting point for worker assignment.

Time Complexity:

• The maxTaskAssign method utilizes binary search, resulting in a time complexity of O(log n), where n is the length of the worker's array. The canCompleteTasks method iterates through tasks and workers, giving an overall complexity of O(n + m), where m is the length of the task array.

Space Complexity:

• The algorithm uses a deque to manage tasks, resulting in an additional space complexity of O(min(n, m)). The array sorting has a space complexity of O(1). Overall, the space complexity is O(min(n, m)).

Java Approach Using Tree Map

Output:

Code Explanation:

• The code implements a binary search algorithm to find the maximum number of tasks that can be assigned to workers under given constraints. It utilizes a TreeMap to manage available workers and their counts, ensuring efficient lookup and removal.
• The validate method checks if tasks can be assigned based on the remaining strength and pills, updating the TreeMap accordingly.
• The binary search narrows down the search space, and the result is the maximum number of tasks that can be assigned while satisfying the given conditions.

Time Complexity:

• The time complexity is O(N log M), where n represents the size of workers' array, and m stands for maximum number of tasks. This complexity is brought about by the binary search and TreeMap operations.

Space Complexity:

• The space complexity is O(N), with N being the length of workers array. The space is employed to store the TreeMap that records free workers and their counts. The amount of extra space used remains the same.