Question

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 1

class Solution:
  def maxTaskAssign(
    self, tasks: List[int], workers: List[int], pills: int, strength: int
  ) -> int:
    def check(x):
      i = 0
      q = deque()
      p = pills
      for j in range(m - x, m):
        while i < x and tasks[i] <= workers[j] + strength:
          q.append(tasks[i])
          i += 1
        if not q:
          return False
        if q[0] <= workers[j]:
          q.popleft()
        elif p == 0:
          return False
        else:
          p -= 1
          q.pop()
      return True

    n, m = len(tasks), len(workers)
    tasks.sort()
    workers.sort()
    left, right = 0, min(n, m)
    while left < right:
      mid = (left + right + 1) >> 1
      if check(mid):
        left = mid
      else:
        right = mid - 1
    return left

class Solution {
  private int[] tasks;
  private int[] workers;
  private int strength;
  private int pills;
  private int m;
  private int n;

  public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
    Arrays.sort(tasks);
    Arrays.sort(workers);
    this.tasks = tasks;
    this.workers = workers;
    this.strength = strength;
    this.pills = pills;
    n = tasks.length;
    m = workers.length;
    int left = 0, right = Math.min(m, n);
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }

  private boolean check(int x) {
    int i = 0;
    Deque<Integer> q = new ArrayDeque<>();
    int p = pills;
    for (int j = m - x; j < m; ++j) {
      while (i < x && tasks[i] <= workers[j] + strength) {
        q.offer(tasks[i++]);
      }
      if (q.isEmpty()) {
        return false;
      }
      if (q.peekFirst() <= workers[j]) {
        q.pollFirst();
      } else if (p == 0) {
        return false;
      } else {
        --p;
        q.pollLast();
      }
    }
    return true;
  }
}

class Solution {
public:
  int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
    sort(tasks.begin(), tasks.end());
    sort(workers.begin(), workers.end());
    int n = tasks.size(), m = workers.size();
    int left = 0, right = min(m, n);
    auto check = [&](int x) {
      int p = pills;
      deque<int> q;
      int i = 0;
      for (int j = m - x; j < m; ++j) {
        while (i < x && tasks[i] <= workers[j] + strength) {
          q.push_back(tasks[i++]);
        }
        if (q.empty()) {
          return false;
        }
        if (q.front() <= workers[j]) {
          q.pop_front();
        } else if (p == 0) {
          return false;
        } else {
          --p;
          q.pop_back();
        }
      }
      return true;
    };
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
};

func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
  sort.Ints(tasks)
  sort.Ints(workers)
  n, m := len(tasks), len(workers)
  left, right := 0, min(m, n)
  check := func(x int) bool {
    p := pills
    q := []int{}
    i := 0
    for j := m - x; j < m; j++ {
      for i < x && tasks[i] <= workers[j]+strength {
        q = append(q, tasks[i])
        i++
      }
      if len(q) == 0 {
        return false
      }
      if q[0] <= workers[j] {
        q = q[1:]
      } else if p == 0 {
        return false
      } else {
        p--
        q = q[:len(q)-1]
      }
    }
    return true
  }
  for left < right {
    mid := (left + right + 1) >> 1
    if check(mid) {
      left = mid
    } else {
      right = mid - 1
    }
  }
  return left
}