#2071

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Number of Tasks You Can Assign

Maximize the number of tasks that can be completed by efficiently using workers and magical pills.

array two pointers binary search greedy queue

Problem Statement

You are given two arrays: tasks and workers. Each task has a strength requirement and each worker has a strength level. A worker can only be assigned to one task if their strength is greater than or equal to the task’s requirement. Additionally, you have magical pills to increase a worker's strength by a fixed amount, with the restriction that each worker can receive at most one pill. The goal is to find the maximum number of tasks that can be completed given the constraints on task assignments and pills.

You need to determine how to optimally allocate tasks to workers, potentially enhancing worker strength with pills, and return the maximum number of tasks that can be completed. This problem involves sorting the tasks and workers, and then applying binary search to find the maximum feasible number of assignments that can be achieved.

Examples

Example 1

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

Output: 3

We can assign the magical pill and tasks as follows:

Give the magical pill to worker 0.
Assign worker 0 to task 2 (0 + 1 >= 1)
Assign worker 1 to task 1 (3 >= 2)
Assign worker 2 to task 0 (3 >= 3)

Example 2

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

Output: 1

We can assign the magical pill and tasks as follows:

Give the magical pill to worker 0.
Assign worker 0 to task 0 (0 + 5 >= 5)

Example 3

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

Output: 2

We can assign the magical pills and tasks as follows:

Give the magical pill to worker 0 and worker 1.
Assign worker 0 to task 0 (0 + 10 >= 10)
Assign worker 1 to task 1 (10 + 10 >= 15) The last pill is not given because it will not make any worker strong enough for the last task.

Constraints

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 104
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 109

Solution Approach

Sort and Binary Search

Start by sorting both the tasks and workers arrays. Then, apply binary search to find the maximum number of tasks that can be completed. The binary search explores the valid answer space, which is the number of tasks that can be assigned to workers considering the strength requirements and the magical pills available.

Greedy Task Allocation with Pills

After determining a possible number of tasks through binary search, use a greedy approach to allocate tasks to workers. Start by assigning tasks to the workers who can complete them without using any pills. Then, distribute the magical pills to workers who need them to meet the task requirements.

Efficiency Considerations

The solution needs to be efficient enough to handle the problem's constraints, where n (number of tasks) and m (number of workers) can both go up to 50,000. The binary search method combined with sorting ensures that the solution runs in O(n log n + m log m) time, which is optimal given the problem's constraints.

Complexity Analysis

Metric	Value
Time	O(n \log n + m \log m + \min(m, n) \log^2 \min(m, n))
Space	O(\log n + \log m + \min(m, n))

The time complexity is dominated by the sorting steps, which are O(n log n) and O(m log m). The binary search runs in O(log n) and the greedy allocation of tasks takes O(n) in the worst case. Thus, the overall time complexity is O(n log n + m log m + min(m, n) log^2 min(m, n)). The space complexity is O(log n + log m + min(m, n)) due to the binary search and helper data structures used during the solution process.

What Interviewers Usually Probe

Checks the candidate's ability to optimize solutions for large input sizes.
Assesses the ability to leverage binary search in an unconventional problem setting.
Evaluates the understanding of greedy algorithms and task allocation optimization.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort both the tasks and workers arrays before applying the binary search.
Misapplying the binary search to the wrong range of possible solutions, resulting in incorrect assignments.
Not optimizing the pill distribution to maximize the number of tasks completed.

Follow-up variants

What if the magical pills have a variable effect on worker strength?
How would the solution change if multiple workers can be assigned to a single task?
How would you modify the solution if the number of magical pills is unlimited?

FAQ

How can I solve the Maximum Number of Tasks You Can Assign problem using binary search?

Start by sorting the tasks and workers. Then, apply binary search over the number of tasks that can be completed, checking feasibility at each step by allocating tasks greedily.

What is the key to optimizing the task allocation in this problem?

The key is to first assign tasks without pills, then use the pills optimally on workers who need a boost to meet task requirements.

How do I manage the pill distribution in this problem?

Pills should be distributed to the weakest workers who are closest to completing their assigned tasks without help, maximizing the number of tasks that can be completed.

What are the time and space complexity of the solution for Maximum Number of Tasks You Can Assign?

The time complexity is O(n log n + m log m + min(m, n) log^2 min(m, n)) and the space complexity is O(log n + log m + min(m, n)).

How does sorting help in solving the Maximum Number of Tasks You Can Assign?

Sorting the tasks and workers helps by allowing a greedy approach to assign tasks in increasing order of difficulty and worker strength, ensuring optimal allocation with pills.

terminal

Solution

Solution 1: Greedy + Binary Search

Sort the tasks in ascending order of completion time and the workers in ascending order of ability.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

class Solution:
    def maxTaskAssign(
        self, tasks: List[int], workers: List[int], pills: int, strength: int
    ) -> int:
        def check(x):
            i = 0
            q = deque()
            p = pills
            for j in range(m - x, m):
                while i < x and tasks[i] <= workers[j] + strength:
                    q.append(tasks[i])
                    i += 1
                if not q:
                    return False
                if q[0] <= workers[j]:
                    q.popleft()
                elif p == 0:
                    return False
                else:
                    p -= 1
                    q.pop()
            return True

        n, m = len(tasks), len(workers)
        tasks.sort()
        workers.sort()
        left, right = 0, min(n, m)
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

Continue Practicing

#2234 maximum total beauty of the gardens #2271 maximum white tiles covered by a carpet #1838 frequency of the most frequent element