2071. Maximum Number of Tasks You Can Assign
About this solution
Maximum Number of Tasks You Can Assign is a unknown-difficulty LeetCode problem covering the Array, Binary Search, Greedy patterns. The Java solution below uses an idiomatic approach that is clean, readable, and directly submittable on LeetCode. Study the logic carefully — recognising the underlying pattern is the key skill that transfers to similar problems in interviews.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
import java.util.*;
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;
}
}