Maximum Number of Tasks You Can Assign

Maximum Number of Tasks You Can Assign

What is this problem about?

The Maximum Number of Tasks You Can Assign coding problem gives you two arrays: tasks (representing the strength required for each task) and workers (representing the strength of each worker). You also have pills (power-up items that temporarily increase a worker's strength by strength_boost) and strength_boost. Each worker can be assigned at most one task, and each task can be assigned to at most one worker. A worker can complete a task if their strength is greater than or equal to the task's requirement. A worker can use at most one pill. You want to find the maximum number of tasks you can assign.

Why is this asked in interviews?

Meta, Amazon, Google, and Bloomberg frequently ask this hard problem because it's a classic example of binary search on the answer combined with a greedy verification function. The verification itself requires careful sorting and a data structure like a multiset or a deque to efficiently find the best worker for a task.

Algorithmic pattern used

Binary Search on the Answer + Greedy Check:

1. Binary Search on Number of Tasks (k): The maximum number of tasks k to assign has a monotonic property: if you can assign k tasks, you can definitely assign any k' < k tasks. This allows for binary searching on k in the range [0, min(len(tasks), len(workers))].
2. check(k) function: Given that we need to assign k tasks, can we do it?
   • Sort both tasks and workers arrays in ascending order.
   • We want to assign the k easiest tasks (tasks[0...k-1]) to the k strongest workers (workers[m-k...m-1]). This greedy choice ensures that if a worker can complete a task, they do it for the easiest possible task, leaving stronger workers for harder tasks.
   • To efficiently assign:
     • Use a multiset (or std::set in C++, or SortedList in Python from sortedcontainers library) to keep track of the available workers' strengths.
     • We'll iterate through the k easiest tasks (tasks[0] to tasks[k-1]).
     • Simultaneously, iterate through the k strongest workers backwards (from workers[m-1] down to workers[m-k]) and add them to our multiset.
     • For each task t = tasks[i] (starting from i=0):
       • Try to find the smallest worker w in multiset such that w >= t.
         • If found, remove w from multiset.
       • Else (no worker can do it without a pill):
         • Try to find the smallest worker w' in multiset such that w' + strength_boost >= t, AND we have pills > 0. This search needs to consider the largest worker that can be boosted to fulfill the task, to save smaller workers for easier tasks.
           • This is typically done by finding the upper_bound(t - strength_boost) in the multiset. If such a worker exists and pills > 0, use a pill, remove the worker, decrement pills.
         • Else (no worker can do it even with a pill): return false.
   • If all k tasks are assigned, return true.

Time Complexity: O((N+M) log (N+M)) due to sorting, and O(k * log k) for the multiset operations inside the check function. Overall: O((N+M) log (N+M) + N * log N * log N). More precisely, it would be O( (N+M) log (N+M) + (N+M) log k * log(max(k, M)) )

Example explanation

tasks = [10, 15, 20], workers = [5, 10, 20, 25], pills = 1, strength_boost = 5. Sort tasks = [10, 15, 20], workers = [5, 10, 20, 25]. Binary search k in [0, min(3, 4) = 3].

Try check(k=2): We need to assign tasks [10, 15] using 2 strongest workers [20, 25]. available_workers = {20, 25}. pills_left = 1.

Task t=10:

• Smallest worker w >= 10: 20. Assign 20. available_workers = {25}. Task t=15:
• Smallest worker w >= 15: 25. Assign 25. available_workers = {}. All 2 tasks assigned. check(2) returns true. So, ans = 2, low = 3.

Try check(k=3): We need to assign tasks [10, 15, 20] using 3 strongest workers [10, 20, 25]. available_workers = {10, 20, 25}. pills_left = 1.

Task t=10:

• Smallest worker w >= 10: 10. Assign 10. available_workers = {20, 25}. Task t=15:
• Smallest worker w >= 15: 20. Assign 20. available_workers = {25}. Task t=20:
• Smallest worker w >= 20: 25. Assign 25. available_workers = {}. All 3 tasks assigned. check(3) returns true. So, ans = 3, low = 4.

Binary search loop terminates (low=4, high=3). ans = 3.

Common mistakes candidates make

• Not using binary search: A naive greedy approach without binary search on k might fail.
• Flawed greedy check function: The greedy choice within check is crucial. It's often "assign easiest task to weakest suitable worker" or "assign hardest task to strongest suitable worker". Efficiently finding the "suitable worker" using data structures is key.
• Incorrect pill usage: Remember that a worker can use at most one pill. Prioritize using pills for tasks that cannot be completed without them.
• Efficiency of multiset operations: Using std::multiset::lower_bound or upper_bound for efficient search.

Interview preparation tip

For the Array Sorting Two Pointers Monotonic Queue Queue Binary Search Greedy interview pattern, this problem exemplifies the "binary search on the answer" technique. The check function often combines sorting, greedy choices, and sometimes advanced data structures for efficient lookups. Practice designing check functions that are both correct and performant.