Assign tasks to workers (with pills giving +strength). Maximize tasks completed.
Input: tasks=[3,2,1], workers=[0,3,3], pills=1, strength=1 → Output: 3
Input: tasks=[5,4], workers=[0,0,0], pills=1, strength=5 → Output: 1
Binary search on answer. For given k tasks/workers, greedily check if feasible using deque and pills optimally.
- Binary search on k (number of tasks to complete)
- For given k: take k easiest tasks and k strongest workers
- Greedily assign: for each worker (weakest first) take smallest feasible task
- Use pill if needed and task still requires it
- Check if all k tasks assigned
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
int lo = 0, hi = Math.min(tasks.length, workers.length);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (canAssign(tasks, workers, pills, strength, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private boolean canAssign(int[] tasks, int[] workers, int pills, int strength, int k) {
TreeMap<Integer, Integer> w = new TreeMap<>();
for (int i = workers.length - k; i < workers.length; i++)
w.merge(workers[i], 1, Integer::sum);
int p = pills;
for (int i = k - 1; i >= 0; i--) {
Integer key = w.floorKey(tasks[i]);
if (key != null) {
w.merge(key, -1, Integer::sum);
if (w.get(key) == 0) w.remove(key);
} else {
if (p == 0) return false;
p--;
key = w.floorKey(tasks[i] - strength);
if (key == null) return false;
w.merge(key, -1, Integer::sum);
if (w.get(key) == 0) w.remove(key);
}
}
return true;
}
- Time Complexity: O(n log^2 n)
- Space Complexity: O(n)