{x}
blog image

Maximum Number of Tasks You Can Assign

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.

 

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 * 104
  • 0 <= pills <= m
  • 0 <= tasks[i], workers[j], strength <= 109

Solution Explanation

This problem asks to find the maximum number of tasks that can be completed given a set of tasks with strength requirements, a set of workers with strengths, a number of pills that can increase a worker's strength, and the strength increase provided by each pill.

The solution employs a binary search approach coupled with a greedy strategy. The core idea is to determine the maximum number of tasks x that can be completed. This is done by checking if it's possible to assign x tasks to workers, considering the pills. The binary search efficiently searches for the optimal value of x.

Algorithm:

  1. Sort: Sort both tasks and workers arrays in ascending order. This is crucial for the efficiency and correctness of the subsequent steps.

  2. Binary Search: Perform a binary search on the range [0, min(n, m)], where n is the number of tasks and m is the number of workers. The binary search aims to find the largest x (number of tasks) such that an assignment is possible.

  3. check(x) function: This function is the heart of the solution. It checks if it's feasible to complete x tasks given the constraints.

    • It uses a deque (q) to store the tasks that are currently unassigned but could potentially be assigned to upcoming workers.
    • It iterates through the workers from the end of the sorted workers array (strongest workers first).
    • For each worker, it checks if any of the unassigned tasks can be completed by the worker (with or without a pill).
    • If a task's strength requirement is less than or equal to the worker's strength, it's considered assigned.
    • If a pill is needed to assign a task to a worker, and pills are available, a pill is used.
    • If a task cannot be assigned to the current worker (no pills left or strength requirement is too high), the function returns false.
    • If all x tasks can be assigned, the function returns true.

  4. Binary Search Update: Based on the result of check(x), the binary search adjusts its boundaries (left and right).

  5. Return Value: The final value of left after the binary search represents the maximum number of tasks that can be assigned.

Time Complexity Analysis:

  • Sorting the tasks and workers arrays takes O(n log n) and O(m log m) time respectively, where n and m are the lengths of the arrays. Since m and n are of similar scale, this dominates the overall time complexity.
  • The binary search iterates log(min(n, m)) times.
  • The check(x) function iterates through at most m workers and x tasks. In the worst case, x can be min(n,m). Therefore, the check(x) function has O(m) time complexity.
  • The overall time complexity is dominated by sorting and is therefore O(n log n + m log m), which simplifies to O(max(n,m) * log(max(n,m))).

Space Complexity Analysis:

  • The space used by the deque q in check(x) is at most O(min(n, m)) in the worst case.
  • The space used for sorting is O(1) in-place sorting for many implementations.
  • The overall space complexity is therefore O(min(n, m)).

Code in Different Languages (already provided in the original response). The code snippets in Python, Java, C++, and Go implement this algorithm efficiently. Note that the use of deque in the check function makes the solution efficient in terms of managing the unassigned tasks. Using a simple array instead could lead to less efficient removals from the middle.