01_Maximum_Number_of_Tasks_You_Can_Assign.cpp

// 2071. 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

class Solution
{
public:
    int maxTaskAssign(vector<int> &tasks, vector<int> &workers, int pills, int strength)
    {
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int left = 0, right = min((int)tasks.size(), (int)workers.size()), answer = 0;

        while (left <= right)
        {
            int mid = (left + right + 1) / 2;
            if (canAssign(tasks, workers, pills, strength, mid))
            {
                answer = mid;
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return answer;
    }

private:
    bool canAssign(vector<int> &tasks, vector<int> &workers, int pills, int strength, int k)
    {
        if (k == 0)
            return true;
        if (k > workers.size())
            return false;

        multimap<int, int> availableWorkers;
        for (int i = workers.size() - k; i < workers.size(); i++)
        {
            availableWorkers.insert({workers[i], i});
        }

        int usedPills = 0;

        for (int i = k - 1; i >= 0; i--)
        {
            int task = tasks[i];

            auto it = prev(availableWorkers.end());
            if (it->first >= task)
            {
                availableWorkers.erase(it);
            }
            else
            {
                auto boostedIt = availableWorkers.lower_bound(task - strength);
                if (boostedIt == availableWorkers.end() || usedPills >= pills)
                {
                    return false;
                }
                availableWorkers.erase(boostedIt);
                usedPills++;
            }
        }

        return true;
    }
};

/*
This solution uses binary search to find the maximum number of tasks that can be assigned.

The maxTaskAssign function:
1. First sorts both tasks and workers arrays
2. Performs binary search on possible number of tasks (0 to min(tasks.size, workers.size))
3. For each mid point, checks if that many tasks can be assigned using canAssign function

The canAssign function:
1. Creates a multimap of available workers for the k strongest workers
2. For each task (from hardest to easiest):
   - Tries to assign strongest available worker
   - If not possible, tries to use a pill on a worker who could complete task with strength boost
   - If neither possible, returns false
3. Returns true if all k tasks can be assigned

Time Complexity: O(n log n) for sorting + O(n log n) for binary search * O(n log n) for canAssign 
                = O(n log^2 n) where n is max(tasks.size, workers.size)
Space Complexity: O(n) for the multimap of available workers
*/