Maximum Number of Tasks You Can Assign

Leetcode Problem:

• Maximum Number of Tasks You Can Assign

Summary

• The problem requires to find the maximum number of tasks that can be completed with given tasks, workers, pills, and strength
• Each task has a strength requirement, each worker has a strength, and there are magical pills that can increase a worker's strength.

Approach

• The solution uses a binary search approach
• It first sorts the tasks and workers arrays
• Then, it performs a binary search between the minimum and maximum possible number of tasks that can be completed
• In each iteration of the binary search, it checks if the current number of tasks can be completed by assigning the workers to the tasks
• If it can, it moves the left pointer to the current number of tasks
• Otherwise, it moves the right pointer to the previous number of tasks
• Finally, it returns the left pointer as the maximum number of tasks that can be completed.

Complexity

• The time complexity of the solution is O(n log n) due to the sorting of the tasks and workers arrays, where n is the number of tasks or workers
• The space complexity is O(n) for the sorting of the tasks and workers arrays.

Explanation

• The solution first sorts the tasks and workers arrays
• Then, it performs a binary search between the minimum and maximum possible number of tasks that can be completed
• In each iteration of the binary search, it checks if the current number of tasks can be completed by assigning the workers to the tasks
• If it can, it moves the left pointer to the current number of tasks
• Otherwise, it moves the right pointer to the previous number of tasks
• Finally, it returns the left pointer as the maximum number of tasks that can be completed
• The solution uses a multiset to keep track of the workers' strength after assigning the magical pills.

Solution Code:

class Solution {
public:
    int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) {
        int left = 0, right = min(tasks.size(), workers.size());

        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        while(left < right) {
            int mid = (left + right + 1) / 2;
            int usedPills = 0;
            multiset workersFree(workers.end() - mid, workers.end());

            bool canAssign = true;
            for(int i = mid - 1; i >= 0; --i) {
                auto it = prev(workersFree.end());

                if(*it < tasks[i]) {
                    it = workersFree.lower_bound(tasks[i] - strength);
                    if(it == workersFree.end()) {
                        canAssign = false;
                        break;
                    }
                    ++usedPills;
                    if(usedPills > pills) {
                        canAssign = false;
                        break;
                    }
                }
                workersFree.erase(it);
            }

            if(canAssign)
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};