[Leetcode] 2071. Maximum Number of Tasks You Can Assign

https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign/description/?envType=daily-question&envId=2025-05-01

initial

So I tried solving the greedy way where if current worker's strength + pill can solve the task, we do that. But this doesnt always fix cuz of 1) premature pill usage 2) strongest worker solving easiest task so later on in the loop we dont have strong workers left

sol

we have to use binary search to guess how many tasks can be solved with the strongest workers. The main logic is assigning k easiest tasks (smallest values from the tasks array) and the k strongest workers (largest values from the workers array)
Then we try to assign tasks, starting with the hardest tasks first. If there is no problem (i.e flag isnt raised), then we can increase this k by putting left at mid Notice its not the usual left=mid+1 cuz we are finding the maximum value.

to find max in binary

https://velog.io/@whitehousechef/Binary-search
so 2 things differ here
1) way to find mid
2) putting left and right is different

continu with sol

Also, we can use bisect left to get the appropriate worker that can do this task with strength pills. But if there is a problem like even after we iter throught the worker array and the bisect left gives the rightmost idx, which means we cant fight a strong worker, or if usedPills == pills and we cannot use another pill, then we flag and break out of loop.

import bisect
class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        ans=0
        workers.sort()
        tasks.sort()
        left,right=0, min(len(tasks),len(workers))
        while left<right:
            mid = (left + right + 1) // 2
            strongestAvailWorkers=workers[-mid:]
            flag=False
            usedPills=0
            for t in reversed(tasks[:mid]):
                if strongestAvailWorkers[-1]>=t:
                    strongestAvailWorkers.pop()
                else:
                    idx=bisect.bisect_left(strongestAvailWorkers,t-strength)
                    if idx==len(strongestAvailWorkers) or usedPills==pills:
                        flag=True
                        break
                    strongestAvailWorkers.pop(idx)
                    usedPills+=1
            if flag:
                right=mid-1
            else:
                left=mid
        return left
        
            

complexity

Sorting takes O(n log n + m log m)
Binary search on the answer takes O(log k) iterations
Each iteration costs O(k log k) because:

We process k tasks/workers
For each task, we might do a binary search (bisect_left) which is O(log k)

So the total complexity is: O(n log n + m log m + log k × k log k)

space is n+m