Problem Description

You have n tasks and m workers. Each task requires a certain strength to complete, stored in array tasks, where tasks[i] is the strength needed for the i-th task. Each worker has a strength value stored in array workers, where workers[j] is the strength of the j-th worker.

To complete a task, a worker must have strength greater than or equal to the task's requirement. Each worker can only be assigned to one task at most.

You also have a limited number of magical pills (given by pills). Each pill increases a worker's strength by exactly strength points. Each worker can take at most one pill.

The goal is to find the maximum number of tasks that can be completed by optimally:

• Assigning workers to tasks (each worker can do at most one task)
• Distributing pills to workers (each worker can take at most one pill)

For example, if you have:

• tasks = [3, 2, 1] (three tasks requiring strengths 3, 2, and 1)
• workers = [0, 3, 3] (three workers with strengths 0, 3, and 3)
• pills = 1 (one pill available)
• strength = 1 (each pill increases strength by 1)

You could give the pill to the first worker (strength becomes 0+1=1), allowing them to complete the task requiring strength 1. The other two workers with strength 3 can complete the tasks requiring strengths 2 and 3. Thus, all 3 tasks can be completed.

The function should return the maximum number of tasks that can be completed given these constraints.

Intuition

The key insight is that if we can complete x tasks, then we can definitely complete x-1, x-2, ..., 1, or 0 tasks. This monotonic property suggests we can use binary search to find the maximum number of tasks we can complete.

First, let's sort both arrays. Sorting tasks in ascending order and workers in ascending order helps us make greedy decisions. When trying to complete x tasks, we should:

• Use the easiest x tasks (the first x tasks after sorting)
• Use the strongest x workers (the last x workers after sorting)

This gives us the best chance of success because we're matching the easiest tasks with our strongest workers.

For the greedy strategy within each check: when we iterate through our selected workers from weakest to strongest, each worker should consider all tasks they could potentially complete (with or without a pill). Among these available tasks:

• If the worker can complete the easiest task without a pill, do it without using a pill (save pills for workers who really need them)
• If the worker needs a pill to complete any task, use the pill to complete the hardest possible task (this maximizes the value we get from the pill)

Why does this greedy approach work? Consider a worker who needs a pill. If we use the pill on this worker to complete an easier task when they could complete a harder one, we might later find that another worker can't complete that harder task even with a pill. By having each worker who uses a pill complete the hardest task they can, we leave easier tasks for subsequent workers who might be able to complete them without pills or with less "waste" of pill strength.

The deque structure helps efficiently track which tasks are available for the current worker - we can add newly available tasks to the back and remove completed tasks from either end depending on whether we used a pill or not.

Learn more about Greedy, Queue, Two Pointers, Binary Search, Sorting and Monotonic Queue patterns.

Solution Approach

The solution uses binary search combined with a greedy assignment strategy.

Step 1: Sorting

tasks.sort()
workers.sort()

Sort both arrays in ascending order to enable greedy decisions.

Step 2: Binary Search Setup

left, right = 0, min(n, m)

We can complete at most min(n, m) tasks (limited by either the number of tasks or workers). Binary search finds the maximum number of tasks we can complete.

Step 3: Binary Search Loop

while left < right:
    mid = (left + right + 1) >> 1
    if check(mid):
        left = mid
    else:
        right = mid - 1

If we can complete mid tasks, try a larger number. Otherwise, try a smaller number.

Step 4: The check(x) Function

This function determines if we can complete exactly x tasks using a greedy strategy:

def check(x):
    i = 0
    q = deque()
    p = pills
    for j in range(m - x, m):

• Use the strongest x workers: workers[m-x] to workers[m-1]
• Process workers from weakest to strongest among these selected workers
• i tracks the next task to consider
• q is a deque storing currently available tasks for worker j
• p tracks remaining pills

For each worker j:

while i < x and tasks[i] <= workers[j] + strength:
    q.append(tasks[i])
    i += 1

Add all tasks that this worker could potentially complete (with a pill) to the deque.

if not q:
    return False

If no tasks are available for this worker, it's impossible to complete x tasks.

if q[0] <= workers[j]:
    q.popleft()

If the worker can complete the easiest available task without a pill, do so. Remove from the front of the deque (smallest task).

elif p == 0:
    return False
else:
    p -= 1
    q.pop()

Otherwise, the worker needs a pill. If no pills remain, return false. If pills are available, use one and complete the hardest available task (remove from the back of the deque).

The greedy logic ensures:

• Workers who don't need pills complete easier tasks
• Workers who need pills complete harder tasks to maximize pill value
• Pills are used only when necessary

The algorithm runs in O((n + m) log(min(n, m)) * min(n, m)) time complexity due to the binary search and the linear check function.

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm works:

Given:

• tasks = [5, 9, 8, 5, 9]
• workers = [1, 6, 4, 2, 6]
• pills = 1
• strength = 5

Step 1: Sort both arrays

• tasks = [5, 5, 8, 9, 9]
• workers = [1, 2, 4, 6, 6]

Step 2: Binary Search We can complete at most min(5, 5) = 5 tasks. Binary search range: [0, 5]

First iteration: mid = 3 (check if we can complete 3 tasks)

• Select easiest 3 tasks: [5, 5, 8]
• Select strongest 3 workers: [4, 6, 6]

Processing workers from weakest to strongest:

• Worker with strength 4:

  • Can potentially complete tasks [5, 5, 8] with pill (4+5=9)
  • Add all to deque: q = [5, 5, 8]
  • Can't complete task 5 without pill (4 < 5)
  • Use pill → strength becomes 9 → complete hardest task (8)
  • Remove 8 from back: q = [5, 5], pills = 0

• Worker with strength 6:

  • No new tasks to add (all were already added)
  • q = [5, 5]
  • Can complete task 5 without pill (6 ≥ 5)
  • Remove 5 from front: q = [5]

• Worker with strength 6:

  • No new tasks to add
  • q = [5]
  • Can complete task 5 without pill (6 ≥ 5)
  • Remove 5 from front: q = []

✓ Successfully completed 3 tasks! Update: left = 3

Second iteration: mid = 4 (check if we can complete 4 tasks)

• Select easiest 4 tasks: [5, 5, 8, 9]
• Select strongest 4 workers: [2, 4, 6, 6]

Processing workers:

• Worker with strength 2:

  • Can potentially complete tasks [5, 5] with pill (2+5=7)
  • Add to deque: q = [5, 5]
  • Can't complete task 5 without pill (2 < 5)
  • Use pill → strength becomes 7 → complete hardest task (5)
  • Remove 5 from back: q = [5], pills = 0

• Worker with strength 4:

  • Can potentially complete task [8] with pill (4+5=9)
  • Add to deque: q = [5, 8]
  • Can't complete task 5 without pill (4 < 5)
  • Need pill but pills = 0 → Return False

✗ Cannot complete 4 tasks! Update: right = 3

Binary search converges: left = right = 3

Answer: 3 tasks can be completed

The key insight illustrated here is how the greedy strategy works:

1. When the worker with strength 4 used the pill in the 3-task scenario, they wisely chose the hardest task (8), leaving easier tasks for stronger workers
2. This allowed the two workers with strength 6 to complete the remaining tasks without pills
3. When we tried 4 tasks, we ran out of pills too early because weaker workers needed them, demonstrating why the greedy pill usage (complete hardest possible task when using a pill) is optimal

Solution Implementation

Time and Space Complexity

Time Complexity: O((n + m) × log(n + m) + min(n, m) × n × log(min(n, m)))

The time complexity breaks down as follows:

• Sorting tasks array: O(n × log n) where n is the number of tasks
• Sorting workers array: O(m × log m) where m is the number of workers
• Binary search runs O(log(min(n, m))) iterations
• For each binary search iteration, the check function is called:
  • The outer loop in check runs x times (at most min(n, m))
  • The inner while loop processes at most x tasks total across all iterations
  • Deque operations (append, popleft, pop) are O(1)
  • Overall check function: O(x) where x ≤ min(n, m)
• Total for binary search with check: O(min(n, m) × log(min(n, m)))

Since sorting dominates when n and m are large, and considering the reference answer simplifies to O(n × log n), this suggests m is treated as comparable to n. The dominant term becomes O(n × log n).

Space Complexity: O(n)

The space complexity consists of:

• The deque q in the check function can hold at most x elements, where x ≤ min(n, m) ≤ n
• Other variables use constant space
• Total space: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Worker Selection Strategy

Pitfall: A common mistake is trying to use the weakest workers first or randomly selecting workers, thinking we should "save" stronger workers for harder tasks.

Why it's wrong: This approach fails because:

• Weak workers might not be able to complete any tasks even with pills
• We waste pills on workers who can't contribute effectively
• We miss opportunities where strong workers could complete tasks without pills

Example:

# WRONG: Using weakest k workers
for worker_index in range(k):  # Starts from weakest workers
    current_worker_strength = workers[worker_index]
    # ... rest of logic

Solution: Always use the strongest k workers when trying to complete k tasks:

# CORRECT: Use strongest k workers
for worker_index in range(num_workers - k, num_workers):
    current_worker_strength = workers[worker_index]
    # ... rest of logic

2. Greedy Pill Usage on Wrong Tasks

Pitfall: When a worker needs a pill, assigning them to the easiest available task (from the front of the deque).

Why it's wrong: This wastes the pill's potential. If we use a pill, we should maximize its value by completing the hardest possible task.

Example:

# WRONG: Using pill on easiest task
if available_tasks[0] <= current_worker_strength:
    available_tasks.popleft()
elif pills_remaining > 0:
    pills_remaining -= 1
    available_tasks.popleft()  # Wrong! Taking easiest task with pill

Solution: When using a pill, assign the worker to the hardest available task:

# CORRECT: Using pill on hardest task
if available_tasks[0] <= current_worker_strength:
    available_tasks.popleft()  # No pill needed, take easiest
elif pills_remaining > 0:
    pills_remaining -= 1
    available_tasks.pop()  # With pill, take hardest task

3. Incorrect Task Availability Window

Pitfall: Adding tasks to the available queue based only on the worker's base strength, or adding all tasks at once.

Why it's wrong:

• We need to consider tasks that the worker could complete WITH a pill
• But we shouldn't add tasks that are too hard even with a pill
• Adding tasks incrementally ensures proper ordering for the greedy strategy

Example:

# WRONG: Only considering base strength
while task_index < k and tasks[task_index] <= current_worker_strength:
    available_tasks.append(tasks[task_index])
    task_index += 1

Solution: Consider the worker's strength with a potential pill:

# CORRECT: Consider strength with pill
while task_index < k and tasks[task_index] <= current_worker_strength + strength:
    available_tasks.append(tasks[task_index])
    task_index += 1

4. Binary Search Boundary Error

Pitfall: Using standard binary search mid calculation which can cause infinite loops or miss the answer.

Example:

# WRONG: Can cause infinite loop when left + 1 == right
while left < right:
    mid = (left + right) // 2  # Floor division
    if can_assign_k_tasks(mid):
        left = mid  # This can cause infinite loop
    else:
        right = mid - 1

Solution: Use ceiling division for mid when updating left = mid:

# CORRECT: Ceiling division prevents infinite loop
while left < right:
    mid = (left + right + 1) // 2  # Ceiling division
    if can_assign_k_tasks(mid):
        left = mid  # Safe now
    else:
        right = mid - 1

These pitfalls often lead to incorrect results or runtime errors. The key insight is that the greedy strategy must be carefully implemented: use the strongest workers, and when pills are needed, maximize their value by completing the hardest possible tasks.