2071. Maximum Number of Tasks You Can Assign

Description

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

 

Solutions

Solution: Binary Search + Monotonic Queue

• Time complexity: O(nlogn+mlogm+min(n,m)*log(min(n,m)))
• Space complexity: O(min(n,m))

 

JavaScript

/**
 * @param {number[]} tasks
 * @param {number[]} workers
 * @param {number} pills
 * @param {number} strength
 * @return {number}
 */
const maxTaskAssign = function (tasks, workers, pills, strength) {
  const n = tasks.length;
  const m = workers.length;
  let left = 0;
  let right = Math.min(n, m);
  let result = 0;

  tasks.sort((a, b) => a - b);
  workers.sort((a, b) => a - b);

  const isCanComplete = assign => {
    const queue = [];
    let worker = m - 1;
    let remainPills = pills;

    for (let index = assign - 1; index >= 0; index--) {
      const task = tasks[index];

      if (queue.length && queue[0] >= task) {
        queue.shift();
      } else if (worker >= 0 && workers[worker] >= task) {
        worker -= 1;
      } else {
        while (worker >= 0 && workers[worker] + strength >= task) {
          queue.push(workers[worker]);
          worker -= 1;
        }

        if (!queue.length || !remainPills) return false;

        queue.pop();
        remainPills -= 1;
      }
    }

    return true;
  };

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (isCanComplete(mid)) {
      result = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
};