Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

If a number of tasks can be assigned, fewer can also be assigned, so binary-search the count. It is enough to test the easiest tasks. Within that test, handle the hardest remaining task first: use the strongest worker without a pill when possible, otherwise boost the weakest worker who can reach its requirement.

Approach

Sort tasks and workers. For a candidate prefix of tasks, copy the worker list and scan that prefix backward. Remove the strongest worker if already strong enough. Otherwise require an unused pill, binary-search the first worker with strength at least task - boost, and remove that worker after using a pill. Reject when no suitable worker exists. Choosing the weakest boostable worker preserves stronger workers for other tasks. Binary-search the largest feasible prefix length; note that the helper receives its last index, so it tests index + 1 tasks. List removal costs are included in the implementation's complexity notes.

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 solve(k):
            p = pills
            w = workers[:]

            for i in range(k, -1, -1):
                if not w:
                    return False
                if w[-1] >= tasks[i]:
                    w.pop()
                else:
                    if p == 0:
                        return False
                    candidate = bisect.bisect_left(w, tasks[i] - strength)
                    if candidate == len(w):
                        return False
                    p -= 1
                    w.pop(candidate)

            return True

        l = 0
        h = n - 1

        while l <= h:
            mid = l + (h - l) // 2
            if solve(mid):
                l = mid + 1
            else:
                h = mid - 1

        return l

Complexity analysis

Let T = tasks.length, W = workers.length, and Q = min(T, W). Both displayed implementations sort the inputs and binary-search the full task-index range, taking worst-case O(T log T + W log W + W * Q * log(T + 1)) time. Each feasibility check copies W workers and uses O(W) auxiliary space; including the runtimes' input-sort workspace, overall peak auxiliary space is O(T + W).