2071. Maximum Number of Tasks You Can Assign LeetCode Solution
In this guide, you will get 2071. Maximum Number of Tasks You Can Assign LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Tasks You Can Assign problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Tasks You Can Assign
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.
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
Complexity Analysis
Time Complexity:
Space Complexity:
2071. Maximum Number of Tasks You Can Assign LeetCode Solution in C++
class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills,
int strength) {
int ans = 0;
int l = 0;
int r = min(tasks.size(), workers.size());
ranges::sort(tasks);
ranges::sort(workers);
// Returns true if we can finish k tasks.
auto canComplete = [&](int k, int pillsLeft) {
// k strongest workers
map<int, int> sortedWorkers;
for (int i = workers.size() - k; i < workers.size(); ++i)
++sortedWorkers[workers[i]];
// Out of the k smallest tasks, start from the biggest one.
for (int i = k - 1; i >= 0; --i) {
// Find the first worker that has strength >= tasks[i].
auto it = sortedWorkers.lower_bound(tasks[i]);
if (it != sortedWorkers.end()) {
if (--(it->second) == 0)
sortedWorkers.erase(it);
} else if (pillsLeft > 0) {
// Find the first worker that has strength >= tasks[i] - strength.
it = sortedWorkers.lower_bound(tasks[i] - strength);
if (it != sortedWorkers.end()) {
if (--(it->second) == 0)
sortedWorkers.erase(it);
--pillsLeft;
} else {
return false;
}
} else {
return false;
}
}
return true;
};
while (l <= r) {
const int m = (l + r) / 2;
if (canComplete(m, pills)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
2071. Maximum Number of Tasks You Can Assign LeetCode Solution in Java
class Solution {
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
int ans = 0;
int l = 0;
int r = Math.min(tasks.length, workers.length);
Arrays.sort(tasks);
Arrays.sort(workers);
while (l <= r) {
final int m = (l + r) / 2;
if (canComplete(tasks, workers, pills, strength, m)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
// Returns true if we can finish k tasks.
private boolean canComplete(int[] tasks, int[] workers, int pillsLeft, int strength, int k) {
// k strongest workers
TreeMap<Integer, Integer> sortedWorkers = new TreeMap<>();
for (int i = workers.length - k; i < workers.length; ++i)
sortedWorkers.merge(workers[i], 1, Integer::sum);
// Out of the k smallest tasks, start from the biggest one.
for (int i = k - 1; i >= 0; --i) {
// Find the first worker that has strength >= tasks[i].
Integer lo = sortedWorkers.ceilingKey(tasks[i]);
if (lo != null) {
sortedWorkers.merge(lo, -1, Integer::sum);
if (sortedWorkers.get(lo) == 0) {
sortedWorkers.remove(lo);
}
} else if (pillsLeft > 0) {
// Find the first worker that has strength >= tasks[i] - strength.
lo = sortedWorkers.ceilingKey(tasks[i] - strength);
if (lo != null) {
sortedWorkers.merge(lo, -1, Integer::sum);
if (sortedWorkers.get(lo) == 0) {
sortedWorkers.remove(lo);
}
--pillsLeft;
} else {
return false;
}
} else {
return false;
}
}
return true;
}
} // code provided by PROGIEZ
2071. Maximum Number of Tasks You Can Assign LeetCode Solution in Python
from sortedcontainers import SortedList
class Solution:
def maxTaskAssign(
self,
tasks: list[int],
workers: list[int],
pills: int,
strength: int,
) -> int:
tasks.sort()
workers.sort()
def canComplete(k: int, pillsLeft: int) -> bool:
"""Returns True if we can finish k tasks."""
# k strongest workers
sortedWorkers = SortedList(workers[-k:])
# Out of the k smallest tasks, start from the biggest one.
for i in reversed(range(k)):
# Find the first worker that has strength >= tasks[i].
index = sortedWorkers.bisect_left(tasks[i])
if index < len(sortedWorkers):
sortedWorkers.pop(index)
elif pillsLeft > 0:
# Find the first worker that has strength >= tasks[i] - strength.
index = sortedWorkers.bisect_left(tasks[i] - strength)
if index < len(sortedWorkers):
sortedWorkers.pop(index)
pillsLeft -= 1
else:
return False
else:
return False
return True
ans = 0
l = 0
r = min(len(tasks), len(workers))
while l <= r:
m = (l + r) // 2
if canComplete(m, pills):
ans = m
l = m + 1
else:
r = m - 1
return ans # code by PROGIEZ
