Problem Informations

• Problem Index: 2071
• Problem Link: Maximum Number of Tasks You Can Assign
• Topics: Array, Binary Search, Greedy, Queue, Sorting, Monotonic Queue

Problem Description

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] \geq 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 \leq n, m \leq 5 \times 10^4$
• $0 \leq pills \leq m$
• $0 \leq tasks[i], workers[j], strength \leq 10^9$

Intuition

The problem involves assigning tasks to workers such that each worker’s strength meets or exceeds the required strength of the assigned task. Additionally, we can use magical pills to temporarily boost a worker’s strength to allow them to complete a task. The central challenge is to maximize the number of tasks that can be completed given these constraints.

A key insight is to leverage a greedy strategy combined with binary search: starting with the simplest cases where no pills are used, and gradually introducing pills only if necessary. We sort both the tasks and workers arrays to orderly manage which worker takes on which task. By using binary search on the number of tasks, we can efficiently find the maximum number of tasks that can be assigned.

Approach

1. Sorting: Begin by sorting the tasks and workers arrays. This helps in easily matching tasks and workers based on strength and ensures the efficient allocation of resources.

2. Binary Search Setup: We want to determine the maximum number of tasks that can be completed given the workers’ strengths and available pills. Set up binary search with left = 0 and right = min(n, m), where n is the number of tasks and m is the number of workers. The goal is to find the maximum value of mid (number of tasks) for which the tasks can be completed.

3. Checking Feasibility with a Helper Function (canDo):

   • For each middle point mid from the binary search, check if mid tasks can be completed.
   • Use a multiset to keep track of the k strongest available workers for the current check, where k = mid.
   • Try to assign each task to the strongest available worker who can complete it without or with a pill. This involves:
     • Checking if a worker can complete the task without a pill using availableWorkers.lower_bound(taskStrength).
     • If not possible, try assigning a pill to a worker using availableWorkers.lower_bound(taskStrength - strength). Decrease the count of available pills if this path is taken.

4. Binary Search Execution:

   • If the current mid number of tasks can be completed, we move the search towards the right (left = mid + 1) to see if more tasks can be handled.
   • If not, adjust the search towards the left (right = mid - 1).

5. Result: Once the binary search concludes, maxTasks will hold the maximum number of tasks that can be completed by optimally distributing workers and pills. Return this value.

By structuring the solution in this manner, we achieve a time-efficient approach making use of sorting and binary search, effectively managing the strength requirements and resource allocations. This method ensures that we are exploring the maximum configuration possible within the constraints provided.

Code

C++

class Solution {
public:
    // Helper function to determine if `k` tasks can be completed.
    bool canDo(int k, const vector<int>& tasks, const vector<int>& workers, int pills, int strength) {
        if (k > tasks.size() || k > workers.size()) return false;

        // Consider the k strongest workers
        multiset<int> availableWorkers(workers.end() - k, workers.end());
        int pillsLeft = pills;

        // Iterate through the tasks that need to be assigned
        for (int i = k - 1; i >= 0; --i) {
            int taskStrength = tasks[i];
            auto it = availableWorkers.lower_bound(taskStrength);
            
            if (it != availableWorkers.end()) {
                availableWorkers.erase(it);
            } else {
                if (pillsLeft == 0) return false;

                // Find a worker who can complete the task with additional strength from a pill
                it = availableWorkers.lower_bound(taskStrength - strength);
                if (it == availableWorkers.end()) return false;
                
                availableWorkers.erase(it);
                --pillsLeft;
            }
        }
        return true;
    }

    // Function to find the maximum number of tasks that can be assigned
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int taskCount = tasks.size();
        int workerCount = workers.size();
        int left = 0, right = min(taskCount, workerCount), maxTasks = 0;

        // Binary search to find the optimal number of tasks
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canDo(mid, tasks, workers, pills, strength)) {
                maxTasks = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return maxTasks;
    }
};

Python

from typing import List
from collections import Counter

class Solution:
    # Helper function to determine if `k` tasks can be completed.
    def canDo(self, k: int, tasks: List[int], workers: List[int], pills: int, strength: int) -> bool:
        if k > len(tasks) or k > len(workers):
            return False

        # Consider the k strongest workers
        availableWorkers = Counter(workers[-k:])
        pillsLeft = pills

        # Iterate through the tasks that need to be assigned
        for i in range(k - 1, -1, -1):
            taskStrength = tasks[i]
            
            it = next((w for w in availableWorkers if w >= taskStrength), None)
            if it is not None:
                availableWorkers[it] -= 1
                if availableWorkers[it] == 0:
                    del availableWorkers[it]
            else:
                if pillsLeft == 0:
                    return False

                # Find a worker who can complete the task with additional strength from a pill
                it = next((w for w in availableWorkers if w >= taskStrength - strength), None)
                if it is None:
                    return False
                
                availableWorkers[it] -= 1
                if availableWorkers[it] == 0:
                    del availableWorkers[it]
                pillsLeft -= 1

        return True

    # Function to find the maximum number of tasks that can be assigned
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        tasks.sort()
        workers.sort()

        taskCount = len(tasks)
        workerCount = len(workers)
        left, right, maxTasks = 0, min(taskCount, workerCount), 0

        # Binary search to find the optimal number of tasks
        while left <= right:
            mid = (left + right) // 2
            if self.canDo(mid, tasks, workers, pills, strength):
                maxTasks = mid
                left = mid + 1
            else:
                right = mid - 1

        return maxTasks

Complexity

• Time complexity: $O(n \log n + m \log m + n \log \min(n, m))$

  The time complexity is derived from several parts of the algorithm:

  1. Sorting the tasks and workers arrays takes $O(n \log n)$ and $O(m \log m)$ respectively.
  2. The binary search on the number of tasks yields a loop with a complexity of $O(\log \min(n, m))$.
  3. The canDo function, which is called during each iteration of the binary search, takes $O(n \log n)$ time in the worst case due to the manipulation of the multiset and iterating over up to $n$ tasks.

  Combining these, the overall time complexity is $O(n \log n + m \log m + n \log \min(n, m))$.

• Space complexity: $O(n)$

  The space complexity is primarily determined by the multiset used in the canDo function, which stores up to $n$ workers in the worst case. Thus, the space complexity is $O(n)$. The use of additional variables and iterators requires constant space, which does not affect the overall space complexity.