你可以安排的最多任务数目

难度: Hard

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成一个任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人最多只能使用一片药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回最多有多少个任务可以被完成。

示例 1：

输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）

示例 2：

输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）

示例 3：

输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）

示例 4：

输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）

提示：

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

Submission

运行时间: 430 ms

内存: 24.4 MB

class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        tl, wl = len(tasks), len(workers)
        tasks.sort()
        workers.sort()
        

        # def check(wsIndex: int) -> bool:
        #     heap = [(w,1) for w in workers[wsIndex:]]
        #     unstrQueue = deque()
        #     total = pills
        #     tlIndex = 0
        #     while heap:
        #         worker, strenged = heappop(heap)
        #         task = tasks[tlIndex]
        #         if task > worker:
                    
        #             if total == 0: return False
        #             total -= 1

        #             if strenged == 1:
        #                 heappush(heap, (worker + strength, 0))
        #                 continue
        #             else:
        #                 while unstrQueue and unstrQueue[0] + strength < task:
        #                     unstrQueue.popleft()
        #                 if unstrQueue: unstrQueue.popleft()
        #                 else: return False

        #         if strenged == 1:
        #             unstrQueue.append(worker)

        #         tlIndex += 1

        #     return True

        def check(wsIndex: int) -> bool:
            stredQueue = deque()
            unstrQueue = deque()
            total = pills
            tlIndex = 0
            while stredQueue or wsIndex < wl:
                worker = -1
                strenged = False
                if wsIndex == wl or (stredQueue and stredQueue[0] <= workers[wsIndex]):
                    strenged = True
                    worker = stredQueue.popleft()
                else:
                    strenged = False
                    worker = workers[wsIndex]
                    wsIndex += 1


                task = tasks[tlIndex]
                if task > worker:
                    
                    if total == 0: return False
                    total -= 1

                    if strenged:
                        while unstrQueue and unstrQueue[0] + strength < task:
                            unstrQueue.popleft()
                        if unstrQueue: unstrQueue.popleft()
                        else: return False
                    else:
                        stredQueue.append(worker + strength)
                        continue
                        

                if not strenged:
                    unstrQueue.append(worker)

                tlIndex += 1

            return True


        left, right = max(0, wl - tl), wl
        while left < right:
            mid = (left + right) >> 1
            if check(mid): right = mid
            else: left = mid + 1

        return wl - right

Explain

此题解使用二分搜索和贪心算法的组合来解决问题。首先，对任务和工人的力量数组进行排序。利用二分搜索尝试找到最大数量的任务可以被完成。对于二分搜索的每个中点，使用check函数来验证是否可以完成至少这么多任务。check函数通过维护两个队列（一个用于已使用药丸增强的工人，一个用于未使用药丸的工人）来尝试分配工人以完成任务，如果任务的力量要求高于当前工人（包括加强后的工人）的力量，就尝试使用药丸。如果不能使用更多的药丸且没有足够力量的工人，则返回失败。通过这种方式，check函数可以判断出在当前二分搜索的中间值下，能否完成任务。最终，二分搜索确定可以完成任务的最大数量。

时间复杂度: O(m log m + n log n)

空间复杂度: O(m)

class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        tl, wl = len(tasks), len(workers)
        tasks.sort()
        workers.sort()
        def check(wsIndex: int) -> bool:
            stredQueue = deque() # 增强工人队列
            unstrQueue = deque() # 未增强工人队列
            total = pills # 剩余药丸数
            tlIndex = 0 # 当前尝试分配的任务索引
            while stredQueue or wsIndex < wl:
                worker = -1
                strenged = False
                if wsIndex == wl or (stredQueue and stredQueue[0] <= workers[wsIndex]):
                    strenged = True
                    worker = stredQueue.popleft()
                else:
                    strenged = False
                    worker = workers[wsIndex]
                    wsIndex += 1
                task = tasks[tlIndex]
                if task > worker:
                    if total == 0: return False # 无药丸且无法完成任务
                    total -= 1
                    if strenged:
                        while unstrQueue and unstrQueue[0] + strength < task:
                            unstrQueue.popleft()
                        if unstrQueue: unstrQueue.popleft()
                        else: return False # 即使使用药丸也无法完成任务
                    else:
                        stredQueue.append(worker + strength)
                        continue
                if not strenged:
                    unstrQueue.append(worker) # 添加到未增强工人队列
                tlIndex += 1
            return True # 成功完成所有任务
        left, right = max(0, wl - tl), wl # 二分搜索范围初始化
        while left < right:
            mid = (left + right) >> 1
            if check(mid): right = mid
            else: left = mid + 1
        return wl - right # 返回最大可能完成的任务数

Explore

任务和工人的力量数组进行排序是为了利用贪心算法的策略，即尽可能地使用最弱的工人来完成最轻的任务，从而最大化完成任务的数量。这种排序确保在分配任务时，可以直接比较任务和工人的力量，简化逻辑并提高效率。排序还有助于在使用二分搜索时，快速确定哪些任务可以被哪些工人完成，以及如何有效地使用药丸。总的来说，排序是实现高效匹配和正确实施贪心策略的关键步骤。

在二分搜索中，中间值mid代表当前尝试分配任务的工人的起始偏移量。这意味着从数组中的mid位置开始，向后的所有工人都可能被用来完成任务。在check函数中，使用这个起始偏移量来确定哪些工人可用，从而根据任务的难度和工人的能力（包括是否使用药丸增强）来决定任务是否可以被完成。如果从mid开始的所有工人配合药丸的使用可以完成任务列表中的足够多任务，则认为这个mid是有效的，二分搜索会尝试更小的mid值以寻找可能的最大任务完成数。

在check函数中，决定是否使用药丸的逻辑基于当前工人的力量与所分配任务的力量需求之间的比较。如果当前工人的力量（即使是已经使用药丸增强过的工人）不足以完成当前任务，且还有剩余的药丸，则会考虑使用一粒药丸。药丸的使用会将工人的力量临时增加一定数值（strength），然后重新评估是否能完成任务。如果使用了药丸后仍不能完成任务或者没有剩余药丸，算法会判断为这个mid值不可行。

如果工人使用药丸后力量增加了strength，但增加后的力量仍不足以完成当前任务，则该任务实际上是无法被当前的工人完成的。在这种情况下，算法会继续寻找下一个可用的工人或继续使用其他药丸增强的工人尝试完成该任务。如果没有更多的工人或药丸可用，这将导致当前的mid值失败，表示从mid开始的工人数无法完成足够多的任务，二分搜索会调整范围尝试一个更大的mid值。