LeetCode 2071 - Maximum Number of Tasks You Can Assign

LeetCode Problem 2071

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Greedy, Queue, Sorting, Monotonic Queue

Solution

Problem Understanding

This problem asks us to maximize the number of tasks that can be completed using a group of workers, where each worker can perform at most one task.

Each task has a required strength value, and each worker has a current strength value. A worker can complete a task if their strength is at least as large as the task requirement.

We are also given a limited number of magical pills. A pill can be given to a worker to temporarily increase their strength by a fixed amount called strength. Each worker can receive at most one pill.

The goal is to determine the maximum number of tasks that can be assigned successfully.

The input consists of:

• tasks[i], the required strength for the ith task
• workers[j], the strength of the jth worker
• pills, the number of pills available
• strength, the bonus strength added by a pill

The output is a single integer representing the maximum number of tasks that can be completed.

The constraints are very important:

• Up to 5 * 10^4 tasks and workers
• Strength values up to 10^9

These limits immediately rule out exponential or factorial assignment approaches. We need something close to O(n log n).

Several edge cases are important:

• There may be more tasks than workers
• Some tasks may be impossible even with pills
• Pills may not be needed at all
• Workers and tasks can contain duplicate values
• A greedy assignment that looks locally optimal may block future assignments

The main challenge is deciding when to use pills and which workers should receive them.

Approaches

Brute Force Approach

A brute force solution would try every possible assignment of workers to tasks and every possible way to distribute pills.

For each task, we could attempt:

• assigning a worker without a pill
• assigning a worker with a pill
• skipping the task

This guarantees correctness because every valid assignment configuration is explored.

However, the number of possible assignments grows combinatorially. Even for moderate input sizes, the number of states becomes enormous.

For example:

• choosing worker-task pairings alone resembles bipartite matching permutations
• pill usage introduces additional branching

The worst case becomes effectively exponential.

With up to 50,000 elements, this is completely infeasible.

Key Insight

The important observation is that we do not need to determine the exact assignment immediately. Instead, we can binary search the answer.

Suppose we ask:

"Can we complete exactly k tasks?"

If we can efficiently answer this question, then we can binary search for the maximum feasible k.

This works because feasibility is monotonic:

• if k tasks are possible, then any smaller number is also possible
• if k tasks are impossible, then any larger number is impossible

The remaining challenge is implementing the feasibility check efficiently.

To maximize success, we should:

• sort tasks from easiest to hardest
• sort workers from weakest to strongest
• attempt to assign the hardest tasks among the selected k
• use pills only when necessary

A greedy strategy works because:

• strong workers should be preserved for hard tasks
• pills should only be used when unavoidable
• among workers capable with a pill, we should use the weakest suitable one

A deque allows us to efficiently manage candidate workers for each task.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all assignments and pill distributions
Optimal	O((n + m) log(n + m))	O(m)	Binary search with greedy feasibility checking

Algorithm Walkthrough

1. Sort tasks and workers

We sort both arrays in ascending order.

This helps because:

• easier tasks should generally go to weaker workers
• harder tasks should be reserved for stronger workers

After sorting:

• tasks[0] is the easiest task
• tasks[-1] is the hardest task
• similarly for workers

2. Binary search the answer

We binary search the maximum number of tasks that can be assigned.

The search range is:

• minimum: 0
• maximum: min(len(tasks), len(workers))

For each midpoint k, we check whether it is possible to assign exactly k tasks.

If feasible:

• try larger values

Otherwise:

• try smaller values

3. Feasibility check for k tasks

To check feasibility:

• take the k easiest tasks
• take the k strongest workers

Why?

If even the strongest workers cannot complete the easiest k tasks, then no assignment can work.

4. Process tasks from hardest to easiest

We iterate through the selected tasks in reverse order.

For each task:

• add all workers that could complete it with a pill into a deque

Condition:

worker + strength >= task

These workers are potential candidates.

5. Greedy assignment

For the current task:

• if the strongest available worker can complete it without a pill, use them
• otherwise, use the weakest worker who can complete it with a pill

This is the crucial greedy step.

Why?

If a worker can already complete the task naturally, using a pill would waste resources.

If a pill is necessary, we use the weakest feasible worker to preserve stronger workers for later tasks.

6. Track pill usage

Whenever a worker requires a pill:

• decrement remaining pills

If pills become negative:

• feasibility fails immediately

7. Continue until all tasks are assigned

If all k tasks are successfully assigned:

• return True

Otherwise:

• return False

Why it works

The correctness relies on a greedy exchange argument.

For the hardest remaining task:

• using the strongest available worker without a pill is always optimal
• if a pill is needed, using the weakest feasible worker preserves stronger workers for future harder tasks

Since tasks are processed from hardest to easiest, future tasks can only become easier. Therefore, preserving stronger workers never hurts.

Binary search works because feasibility is monotonic.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maxTaskAssign(
        self,
        tasks: List[int],
        workers: List[int],
        pills: int,
        strength: int
    ) -> int:

        tasks.sort()
        workers.sort()

        n = len(tasks)
        m = len(workers)

        def can_assign(k: int) -> bool:
            available = deque()
            worker_index = m - k
            remaining_pills = pills

            for task_index in range(k - 1, -1, -1):
                current_task = tasks[task_index]

                while (
                    worker_index < m and
                    workers[worker_index] + strength >= current_task
                ):
                    available.append(workers[worker_index])
                    worker_index += 1

                if not available:
                    return False

                if available[-1] >= current_task:
                    available.pop()
                else:
                    if remaining_pills == 0:
                        return False

                    remaining_pills -= 1
                    available.popleft()

            return True

        left = 0
        right = min(n, m)

        while left < right:
            mid = (left + right + 1) // 2

            if can_assign(mid):
                left = mid
            else:
                right = mid - 1

        return left

The implementation begins by sorting both arrays. This enables the greedy ordering strategy used later.

The can_assign helper determines whether exactly k tasks can be completed.

Inside this helper:

• we consider the k easiest tasks
• we use the k strongest workers

The deque stores workers capable of handling the current task with a pill.

As we move from harder tasks to easier ones:

• more workers become eligible
• workers are inserted into the deque in sorted order

For each task:

• if the strongest worker can do it naturally, we use them
• otherwise, we spend a pill on the weakest feasible worker

Finally, binary search repeatedly calls the feasibility checker until the maximum valid value is found.

Go Solution

package main

import (
	"container/list"
	"sort"
)

func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
	sort.Ints(tasks)
	sort.Ints(workers)

	n := len(tasks)
	m := len(workers)

	canAssign := func(k int) bool {
		deque := list.New()

		workerIndex := m - k
		remainingPills := pills

		for taskIndex := k - 1; taskIndex >= 0; taskIndex-- {
			currentTask := tasks[taskIndex]

			for workerIndex < m &&
				workers[workerIndex]+strength >= currentTask {

				deque.PushBack(workers[workerIndex])
				workerIndex++
			}

			if deque.Len() == 0 {
				return false
			}

			back := deque.Back().Value.(int)

			if back >= currentTask {
				deque.Remove(deque.Back())
			} else {
				if remainingPills == 0 {
					return false
				}

				remainingPills--
				deque.Remove(deque.Front())
			}
		}

		return true
	}

	left := 0
	right := n

	if m < right {
		right = m
	}

	for left < right {
		mid := (left + right + 1) / 2

		if canAssign(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

The Go implementation follows the same algorithmic structure as the Python version.

One notable difference is deque handling. Python provides collections.deque, while Go uses container/list to simulate a double ended queue.

Another difference is type assertions when retrieving values from the linked list:

deque.Back().Value.(int)

Since all strength values fit within 32 bit integer limits, standard Go int arithmetic is safe on LeetCode.

Worked Examples

Example 1

tasks = [3,2,1]
workers = [0,3,3]
pills = 1
strength = 1

After sorting:

tasks   = [1,2,3]
workers = [0,3,3]

Binary search tries k = 2, then k = 3.

Checking k = 3

We use:

tasks   = [1,2,3]
workers = [0,3,3]

Process hardest to easiest.

Task	Eligible Workers Added	Deque	Action
3	3, 3	[3,3]	Use 3 without pill
2	none	[3]	Use 3 without pill
1	0	[0]	Use pill on 0

All tasks assigned successfully.

Answer becomes 3.

Example 2

tasks = [5,4]
workers = [0,0,0]
pills = 1
strength = 5

Sorted:

tasks   = [4,5]
workers = [0,0,0]

Checking k = 2

Hardest task is 5.

Eligible workers:

0 + 5 >= 5

Deque:

[0,0]

Assign one worker using a pill.

Remaining pills:

0

Next task:

4

Remaining worker:

0

Cannot complete without another pill.

Fail.

Checking k = 1

One worker with a pill can complete one task.

Success.

Answer is 1.

Example 3

tasks = [10,15,30]
workers = [0,10,10,10,10]
pills = 3
strength = 10

Sorted arrays remain the same.

Checking k = 3

Hardest task:

30

No worker satisfies:

worker + 10 >= 30

Fail immediately.

Checking k = 2

Tasks:

[10,15]

Workers:

[10,10]

Task	Deque	Action
15	[10,10]	Use pill
10	[10]	No pill needed

Success.

Answer is 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log(n + m))	Sorting dominates, each binary search check is linear
Space	O(m)	Deque stores candidate workers

Sorting requires:

O(n log n + m log m)

The binary search performs at most:

O(log(min(n, m)))

iterations.

Each feasibility check processes workers and tasks linearly, giving:

O(n + m)

per check.

Combining these yields:

O((n + m) log(n + m))

overall.

Test Cases

sol = Solution()

# Provided examples
assert sol.maxTaskAssign([3, 2, 1], [0, 3, 3], 1, 1) == 3  # all tasks possible
assert sol.maxTaskAssign([5, 4], [0, 0, 0], 1, 5) == 1  # only one task possible
assert sol.maxTaskAssign([10, 15, 30], [0, 10, 10, 10, 10], 3, 10) == 2  # hardest impossible

# No pills needed
assert sol.maxTaskAssign([1, 2], [2, 3], 0, 5) == 2  # workers already strong enough

# No tasks possible
assert sol.maxTaskAssign([100], [1], 0, 10) == 0  # insufficient strength

# More workers than tasks
assert sol.maxTaskAssign([2, 2], [1, 2, 3, 4], 1, 1) == 2  # extra workers available

# More tasks than workers
assert sol.maxTaskAssign([1, 2, 3, 4], [4, 4], 0, 0) == 2  # limited by workers

# Pill required exactly
assert sol.maxTaskAssign([5], [2], 1, 3) == 1  # exact boosted strength

# Pill still insufficient
assert sol.maxTaskAssign([10], [1], 1, 5) == 0  # even boosted worker too weak

# Duplicate tasks and workers
assert sol.maxTaskAssign([4, 4, 4], [3, 3, 3], 3, 1) == 3  # all require pills

# Zero strength boost
assert sol.maxTaskAssign([3, 3], [3, 2], 1, 0) == 1  # pill provides no help

# Large pill supply
assert sol.maxTaskAssign([5, 6, 7], [1, 2, 3], 10, 10) == 3  # enough pills for everyone

# Empty feasible subset
assert sol.maxTaskAssign([100, 200], [1, 2], 0, 0) == 0  # no valid assignments

Test Summary

Test	Why
Example 1	Validates full assignment with one pill
Example 2	Validates partial assignment only
Example 3	Validates impossible hardest task
No pills needed	Ensures greedy does not waste pills
No tasks possible	Handles total failure correctly
More workers than tasks	Ensures extra workers are ignored properly
More tasks than workers	Result limited by worker count
Pill required exactly	Verifies equality edge case
Pill still insufficient	Verifies impossible boosted assignment
Duplicate tasks and workers	Handles repeated values correctly
Zero strength boost	Ensures useless pills do not break logic
Large pill supply	Verifies many boosted assignments
Empty feasible subset	Ensures binary search can return zero

Edge Cases

One important edge case occurs when no task can be completed, even with pills. For example:

tasks = [100]
workers = [1]
pills = 1
strength = 5

A naive implementation might incorrectly assume that having pills always guarantees at least one assignment. The feasibility check correctly rejects the worker because:

1 + 5 < 100

The deque remains empty, and the function immediately returns False.

Another important case is when pills provide no benefit because strength = 0. In this situation, pills should behave as useless resources. Some implementations accidentally consume pills unnecessarily or treat boosted workers differently even though no improvement occurs. This solution only uses pills when a worker cannot naturally complete the task, so correctness is preserved.

Duplicate values are also important. Multiple tasks and workers may share identical strengths. Some greedy implementations fail because they rely on uniqueness assumptions or unstable ordering. Since this algorithm works entirely on sorted arrays and relative comparisons, duplicates are handled naturally and correctly.

A subtle edge case appears when a strong worker could complete an easy task while a weaker worker would require a pill. A poor greedy choice may waste strong workers early and leave impossible hard tasks later. Processing tasks from hardest to easiest avoids this issue because difficult tasks are prioritized first.