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)
Example 4:
Input: tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
Output: 3
Explanation:
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 * 104
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 109
Solution: Greedy + Binary Search in Binary Search.
Find the smallest k, s.t. we are NOT able to assign. Then answer is k- 1.
The key is to verify whether we can assign k tasks or not.
Greedy: We want k smallest tasks and k strongest workers.
Start with the hardest tasks among (smallest) k:
1. assign task[i] to the weakest worker without a pill (if he can handle the hardest work so far, then the stronger workers can handle any simpler tasks left)
2. If 1) is not possible, we find a weakest worker + pill that can handle task[i] (otherwise we are wasting workers)
3. If 2) is not possible, impossible to finish k tasks.
Let k = min(n, m)
Time complexity: O((logk)2 * k)
Space complexity: O(k)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Author: Huahua class Solution { public: int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { const int n = tasks.size(); sort(begin(tasks), end(tasks)); sort(begin(workers), end(workers)); auto check = [&](int k) { multiset<int> ws(rbegin(workers), rbegin(workers) + k); for (int i = k - 1, p = 0; i >= 0; --i) { auto it = ws.lower_bound(tasks[i]); if (it != end(ws)) { ws.erase(it); } else if ((it = ws.lower_bound(tasks[i] - strength)) != end(ws)) { if (++p > pills) return false; ws.erase(it); } else { return false; } } return true; }; int l = 0; int r = min(tasks.size(), workers.size()) + 1; while (l < r) { int m = l + (r - l) / 2; if (!check(m)) { r = m; } else { l = m + 1; } } return l - 1; } }; |