##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2071.html

# 2071. Maximum Number of Tasks You Can Assign (Hard)

You have `n`

tasks and `m`

workers. Each task has a strength requirement stored in a **0-indexed** integer array `tasks`

, with the `i`

task requiring ^{th}`tasks[i]`

strength to complete. The strength of each worker is stored in a **0-indexed** integer array `workers`

, with the `j`

worker having ^{th}`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], workers = [1,0,3], pills = 1, strength = 13Output:3Explanation: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 = [,4], workers = [5,0,0], pills = 1, strength = 50Output:1Explanation: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,30], workers = [15,0,10,10,10], pills = 3, strength = 1010Output:2Explanation: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)

**Example 4:**

Input:tasks = [,9,5,8,9], workers = [1,5,6,2,4], pills = 1, strength = 56Output:3Explanation:We can assign the magical pill and tasks as follows: - Give the magical pill to worker 2. - Assign worker 1 to task 0 (6 >= 5) - Assign worker 2 to task 2 (4 + 5 >= 8) - Assign worker 4 to task 3 (6 >= 5)

**Constraints:**

`n == tasks.length`

`m == workers.length`

`1 <= n, m <= 5 * 10`

^{4}`0 <= pills <= m`

`0 <= tasks[i], workers[j], strength <= 10`

^{9}

**Companies**:

Facebook

**Related Topics**:

Array, Binary Search, Greedy, Queue, Sorting, Monotonic Queue

**Similar Questions**:

## Solution 1. Binary Answer

```
// OJ: https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign/
// Time: O(log(min(T, W)) * WlogW)
// Space: O(W)
// Ref: https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign/discuss/1575887/C%2B%2B-or-Binary-Search-%2B-Intuitive-Greedy-Idea-or-Detailed-Explanation-%2B-Comments
class Solution {
public:
int maxTaskAssign(vector<int>& T, vector<int>& W, int P, int S) {
sort(begin(T), end(T));
sort(begin(W), end(W));
auto valid = [&](int cnt) {
multiset<int> s(begin(W), end(W));
int match = 0;
bool ans = true;
for (int i = cnt - 1; i >= 0; --i) {
if (T[i] <= *s.rbegin()) {
s.erase(prev(s.end()));
} else {
auto it = s.lower_bound(T[i] - S);
if (it != s.end()) {
++match;
s.erase(it);
} else {
ans = false;
break;
}
}
if (match > P) {
ans = false;
break;
}
}
return ans;
};
int L = 0, R = min(T.size(), W.size());
while (L <= R) {
int M = (L + R) / 2;
if (valid(M)) L = M + 1;
else R = M - 1;
}
return R;
}
};
```