Maximum Number of Tasks You Can Assign | Leetcode 2071

class Solution {
    bool canAssign(int mid,vector<int>& workers,vector<int>& tasks,int pills,int strength){
        multiset<int> usable_workers(workers.end()-mid,workers.end());
        for(int i=mid-1;i>=0;--i){
            auto curr_worker = --usable_workers.end();

            if(*curr_worker < tasks[i]){
                if(pills<=0)    return false;
                
                //Optimal Strategy: Assign weakest worker to get the current task done
                auto weakest_worker = usable_workers.lower_bound(tasks[i]-strength);
                if(weakest_worker==usable_workers.end())
                    return false;//No one can be assigned the current job (even using pill)
                
                pills--;
                usable_workers.erase(weakest_worker);
            }else
                usable_workers.erase(curr_worker);
        }
        return true;
    }
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        sort(workers.begin(),workers.end());
        sort(tasks.begin(),tasks.end());
        int low = 0;
        int high = min(tasks.size(),workers.size());
        int mid;

        int assigned = 0;
        while(low <= high){
            mid = low+(high-low)/2;
            if(canAssign(mid,workers,tasks,pills,strength)){
                assigned = mid;
                low = mid+1;
            }else
                high = mid-1;
        }
        return assigned;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    private boolean canAssign(int mid, List<Integer> workers, List<Integer> tasks, int pills, int strength) {
        TreeSet<Integer> usableWorkers = new TreeSet<>();
        int n = workers.size();
        for (int i = n - mid; i < n; i++) {
            usableWorkers.add(workers.get(i));
        }
        
        for (int i = mid - 1; i >= 0; --i) {
            int task = tasks.get(i);
            Integer currWorker = usableWorkers.last();
            
            if (currWorker < task) {
                if (pills <= 0) {
                    return false;
                }
                
                // Find the weakest worker who can do the task with pill
                Integer weakestWorker = usableWorkers.ceiling(task - strength);
                if (weakestWorker == null) {
                    return false;
                }
                
                pills--;
                usableWorkers.remove(weakestWorker);
            } else {
                usableWorkers.remove(currWorker);
            }
        }
        return true;
    }
    
    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        Arrays.sort(tasks);
        Arrays.sort(workers);
        
        List<Integer> taskList = new ArrayList<>();
        List<Integer> workerList = new ArrayList<>();
        for (int task : tasks) taskList.add(task);
        for (int worker : workers) workerList.add(worker);
        
        int low = 0;
        int high = Math.min(tasks.length, workers.length);
        int assigned = 0;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canAssign(mid, workerList, taskList, pills, strength)) {
                assigned = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return assigned;
    }
}

#Python
import bisect

class Solution:
    def canAssign(self, mid, workers, tasks, pills, strength):
        usable_workers = sorted(workers[-mid:])
        for i in range(mid - 1, -1, -1):
            task = tasks[i]
            if usable_workers[-1] >= task:
                usable_workers.pop()
            else:
                if pills <= 0:
                    return False
                # Find the weakest worker who can do the task with pill
                idx = bisect.bisect_left(usable_workers, task - strength)
                if idx == len(usable_workers):
                    return False
                pills -= 1
                usable_workers.pop(idx)
        return True
    
    def maxTaskAssign(self, tasks, workers, pills, strength):
        tasks.sort()
        workers.sort()
        low, high = 0, min(len(tasks), len(workers))
        assigned = 0
        
        while low <= high:
            mid = low + (high - low) // 2
            if self.canAssign(mid, workers, tasks, pills, strength):
                assigned = mid
                low = mid + 1
            else:
                high = mid - 1
        return assigned
*/

In java implementation we have to use TreeMap instead of TreeSet.
This is a workable java implementation.

private boolean canAssign(int mid, int[] workers, int[] tasks, int pills, int strength) {
        TreeMap<Integer, Integer> usableWorkers = new TreeMap<>();
        int n = workers.length;
        for (int i = n - mid; i < n; i++)
            usableWorkers.put(workers[i], usableWorkers.getOrDefault(workers[i], 0) + 1);

        for (int i = mid - 1; i >= 0; --i) {
            int task = tasks[i];
            Integer currWorker = usableWorkers.lastKey();
            
            if (currWorker < task) {
                if (pills <= 0)
                    return false;
                
                // Find the weakest worker who can do the task with pill
                Integer weakestWorker = usableWorkers.ceilingKey(task - strength);
                if (weakestWorker == null)
                    return false;
                
                pills--;

                usableWorkers.put(weakestWorker, usableWorkers.get(weakestWorker) - 1);
                if (usableWorkers.get(weakestWorker) == 0)
                    usableWorkers.remove(weakestWorker);

            } else {
                usableWorkers.put(currWorker, usableWorkers.get(currWorker) - 1);
                if (usableWorkers.get(currWorker) == 0)
                    usableWorkers.remove(currWorker);
            }
        }
        return true;
}

public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        Arrays.sort(tasks);
        Arrays.sort(workers);
        
        int low = 0;
        int high = Math.min(tasks.length, workers.length);
        int assigned = 0;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canAssign(mid, workers, tasks, pills, strength)) {
                assigned = mid;
                low = mid + 1;
            } else
                high = mid - 1;
        }
        return assigned;
}