Maximum Number of Tasks You Can Assign

Problem

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.

Examples

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̲,1̲0̲,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^4
• 0 <= pills <= m
• 0 <= tasks[i], workers[j], strength <= 10^9

Solution

Method 1 - Using Deque + Binary Search

The approach stems from using binary search combined with a greedy algorithm to determine the maximum number of tasks that can be completed. Here's the breakdown:

1. Sorting:
   • Sort both tasks and workers so that tasks are matched optimally (easiest task to weakest worker).
   • Sorting ensures easier pairing, both with and without pills.
2. Binary Search:
   • Define the search range as [0, min(n, m)], where n is the number of tasks and m is the number of workers.
   • For each mid value (number of tasks being tested):
     • Check if it's feasible to assign mid tasks using the workers and pills available.
     • Adjust the bounds (l, h) based on feasibility.
3. Feasibility Check (canComplete):
   • Use a deque (double-ended queue) to manage workers capable of being boosted with pills (those within range of task difficulty).
   • Assign tasks starting from the hardest task downwards:
     • If a worker (from the end of deque) can finish the task without a pill, assign the worker directly.
     • Else if pills are feasible, assign the weakest worker in the deque and use a pill.
     • Break early if no feasible worker exists for a task.
4. Optimisation:
   • Always prioritise workers who do not need pills first and conserve pills for tasks that cannot otherwise be completed.

Code

Java

class Solution {

    public int maxTaskAssign(
        int[] tasks,
        int[] workers,
        int pills,
        int strength
    ) {
        Arrays.sort(tasks);
        Arrays.sort(workers);
        int l = 0, h = Math.min(tasks.length, workers.length), ans = 0;

        while (l <= h) {
            int mid = (l + h) / 2;
            if (canComplete(mid, tasks, workers, pills, strength)) {
                ans = mid; // Update the result if feasible
                l = mid + 1; // Try higher task count
            } else {
                h = mid - 1; // Try lower task count
            }
        }
        return ans;
    }

    private boolean canComplete(
        int count,
        int[] tasks,
        int[] workers,
        int pills,
        int strength
    ) {
        Deque<Integer> dq = new ArrayDeque<>();
        int j = workers.length - 1;

        // Iterate through tasks from the hardest (for the current subset of tasks)
        for (int i = count - 1; i >= 0; i--) {
            // Add workers to deque that can be boosted with pills to complete tasks
            while (
                j >= workers.length - count && workers[j] + strength >= tasks[i]
            ) {
                dq.addFirst(workers[j]);
                j--;
            }
            if (dq.isEmpty()) {
                return false; // No worker can handle the current task
            } else if (dq.peekLast() >= tasks[i]) {
                dq.pollLast(); // Assign the strongest worker available without a pill
            } else {
                if (pills == 0) {
                    return false; // No pills left to boost the worker's strength
                }
                dq.pollFirst(); // Use pill on weakest worker
                pills--;
            }
        }
        return true; // All tasks can be handled
    }
}

Python

class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        # Sort tasks and workers for greedy pairing
        tasks.sort()
        workers.sort()
        
        # Binary search to find maximum number of tasks
        l, h, ans = 0, min(len(tasks), len(workers)), 0
        
        while l <= h:
            mid = (l + h) // 2
            if self.canComplete(mid, tasks, workers, pills, strength):
                ans = mid  # Update result
                l = mid + 1  # Try higher task count
            else:
                h = mid - 1  # Try lower task count
        
        return ans

    def canComplete(self, count: int, tasks: List[int], workers: List[int], pills: int, strength: int) -> bool:
        # Double-ended queue to store workers useful for boosting
        dq = deque()
        j = len(workers) - 1
        
        # Iterate from hardest task down to easiest
        for i in range(count - 1, -1, -1):
            # Push workers who can be boosted to the deque
            while j >= len(workers) - count and workers[j] + strength >= tasks[i]:
                dq.appendleft(workers[j])
                j -= 1
            
            # No worker left for current task
            if not dq:
                return False
            # Assign strongest worker without a pill
            elif dq[-1] >= tasks[i]:
                dq.pop()
            # Use a pill and assign weakest worker
            else:
                if pills == 0:
                    return False  # No pills left
                dq.popleft()
                pills -= 1
        
        return True  # All tasks can be handled

Complexity

• ⏰ Time complexity: O(n * log(n) + m * log(m) + n*log(min(n, m))) where n is number of workers and m is number of tasks
  • Sorting tasks and workers: O(n * log(n) + m * log(m))
  • Binary search iterations: At most O(n) checks.
  • Feasibility check complexity: O(n) using deque operations.
  • Total: O(n * log(n) + m * log(m) + n^2) (worst-case).
• 🧺 Space complexity: O(n) for using Deque.