Welcome to Subscribe On Youtube
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.lengthm == workers.length1 <= n, m <= 5 * 1040 <= pills <= m0 <= tasks[i], workers[j], strength <= 109
Solutions
-
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; } }; -
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 -
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 }