Maximum Number of Tasks You Can Assign

Share

Assign tasks to workers (with pills giving +strength). Maximize tasks completed.

Example 1
Input: tasks=[3,2,1], workers=[0,3,3], pills=1, strength=1 → Output: 3
Example 2
Input: tasks=[5,4], workers=[0,0,0], pills=1, strength=5 → Output: 1

Solution Approach

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
Java
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)