How do you solve Maximum Number of Tasks You Can Assign on LeetCode?

Maximum Number of Tasks You Can Assign (LeetCode #2071) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n + m log m) time complexity and O(1) space complexity. Key insight: Sorting helps in efficiently matching tasks to workers.

What is the brute force solution for Maximum Number of Tasks You Can Assign?

The brute force approach for Maximum Number of Tasks You Can Assign is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking every possible assignment of workers to tasks, considering both their strengths and the option to use magical pills. This method is straightforward but inefficient, as it explores all combinations. The optimal Optimal Solution approach improves this to O(n log n + m log m).

What are the interview tips for Maximum Number of Tasks You Can Assign?

Always discuss your thought process before coding. Consider edge cases, such as when there are more tasks than workers. Practice explaining your code as you write it.

What are common mistakes when solving Maximum Number of Tasks You Can Assign?

Not considering the use of pills effectively. Failing to sort the tasks and workers arrays.

#2071

Maximum Number of Tasks You Can Assign

Hard

ArrayTwo PointersBinary SearchGreedyQueueSortingMonotonic QueueTwo PointersGreedySorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n + m log m)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n + m log m)Space O(1)

The optimal approach uses sorting and a two-pointer technique to efficiently assign workers to tasks. By sorting both arrays, we can quickly determine how many tasks can be completed with and without using pills.

⚙️

Algorithm

3 steps

1Step 1: Sort both tasks and workers arrays.
2Step 2: Use two pointers to iterate through tasks and workers, trying to assign workers to tasks based on their strengths.
3Step 3: If a worker cannot complete a task, check if they can complete it with a pill and adjust the count of available pills accordingly.

solution.py23 lines

1# Full working Python code
2
3def maxTasks(tasks, workers, pills, strength):
4    tasks.sort()
5    workers.sort()
6    completed = 0
7    i, j = 0, 0
8    while i < len(tasks) and j < len(workers):
9        if workers[j] >= tasks[i]:
10            completed += 1
11            i += 1
12            j += 1
13        elif pills > 0 and workers[j] + strength >= tasks[i]:
14            completed += 1
15            pills -= 1
16            i += 1
17            j += 1
18        else:
19            j += 1
20    return completed
21
22# Example usage
23print(maxTasks([3, 2, 1], [0, 3, 3], 1, 1))  # Output: 3

ℹ

Complexity note: The time complexity is dominated by the sorting steps, which are O(n log n) for tasks and O(m log m) for workers, where n is the number of tasks and m is the number of workers.

1Sorting helps in efficiently matching tasks to workers.
2Using pills strategically can maximize task completion.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.