<p>You have <code>n</code> tasks and <code>m</code> workers. Each task has a strength requirement stored in a <strong>0-indexed</strong> integer array <code>tasks</code>, with the <code>i<sup>th</sup></code> task requiring <code>tasks[i]</code> strength to complete. The strength of each worker is stored in a <strong>0-indexed</strong> integer array <code>workers</code>, with the <code>j<sup>th</sup></code> worker having <code>workers[j]</code> strength. Each worker can only be assigned to a <strong>single</strong> task and must have a strength <strong>greater than or equal</strong> to the task&#39;s strength requirement (i.e., <code>workers[j] &gt;= tasks[i]</code>).</p>

<p>Additionally, you have <code>pills</code> magical pills that will <strong>increase a worker&#39;s strength</strong> by <code>strength</code>. You can decide which workers receive the magical pills, however, you may only give each worker <strong>at most one</strong> magical pill.</p>

<p>Given the <strong>0-indexed </strong>integer arrays <code>tasks</code> and <code>workers</code> and the integers <code>pills</code> and <code>strength</code>, return <em>the <strong>maximum</strong> number of tasks that can be completed.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tasks = [<u><strong>3</strong></u>,<u><strong>2</strong></u>,<u><strong>1</strong></u>], workers = [<u><strong>0</strong></u>,<u><strong>3</strong></u>,<u><strong>3</strong></u>], pills = 1, strength = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong>
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 &gt;= 1)
- Assign worker 1 to task 1 (3 &gt;= 2)
- Assign worker 2 to task 0 (3 &gt;= 3)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tasks = [<u><strong>5</strong></u>,4], workers = [<u><strong>0</strong></u>,0,0], pills = 1, strength = 5
<strong>Output:</strong> 1
<strong>Explanation:</strong>
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 &gt;= 5)
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> tasks = [<u><strong>10</strong></u>,<u><strong>15</strong></u>,30], workers = [<u><strong>0</strong></u>,<u><strong>10</strong></u>,10,10,10], pills = 3, strength = 10
<strong>Output:</strong> 2
<strong>Explanation:</strong>
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 &gt;= 10)
- Assign worker 1 to task 1 (10 + 10 &gt;= 15)
The last pill is not given because it will not make any worker strong enough for the last task.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == tasks.length</code></li>
	<li><code>m == workers.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= pills &lt;= m</code></li>
	<li><code>0 &lt;= tasks[i], workers[j], strength &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        # HARD problem, tried a bunch of things but can't get something to work in linear or linearithmic time

        # T = len(tasks)
        # W = len(workers)
        # tasks.sort(reverse=True)
        # workers.sort(reverse=True)


        # key insight: suppose there's a task we could do with a worker and a pill
        #    should we spend the pill? case A: If there's a later task the worker can do then maybe
        #                              case B: if there's no later task then definitely yes, otherwise the task will not be done
        #
        # each pill at most can let us accomplish 1 whole new task (it may take multiple pills per task)
        # so we can greedily spend 1 pill per task

        # let's return to case A:

        #  we saw t1 > w1 >= t2
        #
        #        if there's a later worker that can do t2 then pop that worker and do it
        #
        #        if there's a later worker that needs a pill for 
        #
        #        t1      t2   t3     t4
        #           w1 w2        w3

        # seems like a pending stack question, e.g. look at next worker and task
        #     if worker can do it then assign and proceed
        #     otherwise push both to stacks to form a "zipper" like t1,w1 t3,w3 as done above
        #          at some point we'll end with an excess of tasks or an excess of workers

        #  excess tasks: t1                t2    t3 t4
        #                   w1                w2
        #      > spend no pills, each worker has a task

        # excess workers

        #       t1           t2       t3
        #         w1           w2                        w3

        # if we can "zipper" numUnassignedTasks
        # then proceed

        # don't know, don't care, give up, there's a pattern or crazy clever insight I'm missing and I'm not going to find it at this point

        # or...
        #     gap between tasks and workers doesn't matter
        #     if curr worker is strong enough to handle next task, assign and move on
        #     if curr worker is too weak even with a pill, discard task

        #  will result in t1        t2             t3     t4     t5
        #                   w1           w2          w3      w4     w5
        #
        # skip remaining tasks
        #
        # if there is a pill for every worker at this point then spend that number of pills to gain one more task
        # otherwise tasks-1

        # except this fails on example 2 X(

        
        #### brute force, then optimize?

        # suppose we sort descending
        #  then we want to know the max we can do of t: and w: with p pills left

        # @cache
        # def most(t: int, w: int, p: int):
        #     if t == T or w == W: return 0

        #     if workers[w] >= tasks[t]: return most(t+1, w+1, p)
            
        #     best = most(t+1, w, p) # can always skip
        #     if workers[w] + strength >= tasks[t]:
        #         best = max(best, 1 + most(t+1, w+1, p-1)) # this seems strictly better


        #### HOLD UP  A SECOND:
        #      if we have t1    t2
        #                    w1     w2
        #   if strength is big then we can spent one pill on w2 to fix w2, better than the zipper I was thinking of before!!!

        # so maybe the loop is
        #      for each task:
        #        find min remaining worker, if any, such that worker[w]+strength >= task
        #        then assign
        #         that will increase completed tasks

        #    t1    t2
        #       w1    w2



        ##### other idea
        #   workers that can't be assigned to any task are useless

        # so maybe we sort ascending
        #   and as we find workers we can't use, put them in a deque
        #
        # iter through tasks and workers in order
        #
        #  w1  w2   w3       w4   w5
        #                t1          t2
        #

        ##### trying again after a few hours

        # top-down DFS, then bottom-up DP with optimizations

        #     t1 t2
        #       w1 w2
        #
        # my algo says 2 pills needed for tw
        # but reality is we only need one pill, for w2 + strength > t1 and then w1 > t2

        # so the optimal matching is NOT in index order

        # want to maximize count of tasks "behind" workers after using pills
        #
        # so maybe for each task in order we try to find a worker without pills that can handle it
        # if not, then see if we can promote a worker with pills

        # problem: suppose we have
        #    t1   t2        t3
        #  w1   w2    w3  w4
        #
        # if we burn a pill on w1 then we get w1+p -- t1, and then  w3--t2: 2 jobs
        #    but best is w1--t1 w3--t2 w4+p--t3 for 3 jobs

        # what we need to do is look at cumulative workers with strength >= current job; if there's
        # not enough then using a pill will help
        #   not enough, and using a pill helps: still might not be optimal
        #
        #                t1              t2    t3   t4
        #            w1      w2       w3
        #
        # t1: not enough workers left, so we'd think promoting w1 with pill would help. But really w2 covers it
        #     meanwhile w3 can't be promoted

        # without pills
        #   for each task: assign to worker if possible, else ditch it

        ######## TIME FOR HINTS

        # 1. Is it possible to assign the first k smallest tasks to the workers?
        
        # for smallest task: is there a stronger worker?
        #   for next smallest task: is there a next worker?
        #     and so on, two-pointer

        # suppose we do that, but then we also keep track of workers we skipped along the way
        
        # then at each point we have to decide if we'll use a pill

        #  t1    t2                   t3    t4   t5    t6 t7
        # w1         w2 w3             w4 w5  w6      w7
        #             * *              *      *       *

        # 2. How can you efficiently try every k?

        # I just did the algo, it's a two-pointer...

        # Maybe 1. refers to using pills?

        # I think the point of 1. is that if we we can assign any k tasks it's going to be the lowest k

        ###### So how can we tell if we can do the first k with any number of pills?

        # IS IT GUESS AND CHECK???????

        # suppose we can do k
        #     then there should be a bijection between workers and the lowest k tasks
        

        # how can we verify we can do k?

        # keep in mind nasty edge cases like this:
        #     strength = 5
        #
        #     tasks:          5   6        9
        #     workers: 3 4           7   
        #
        #
        # right answer: promote 3 -> 8, 4 -> 9

        # idea is that we'll use top k workers and bottom k tasks, there will be a bijection
        #
        # for lowest task we need all k >= after using pills
        # 

        # after much wrangling, tracking the numbers explicitly isn't working, too complicated, edge cases

        # can we something dumb like reduce the task cost by strength instead of increasing workers?
        #   nope, same corner cases

        # last attept for tonight
        #   track cumulative workers stronger than each task, including pills used

        # for the example above:
        #       5: 1 worker >=, so we need to spend 2 pills
        #          promote 3 and 4 to 8 and 9
        #
        #     now 5, expecting 3 tasks above, has 3. good
        #
        #         6: expects 2 >=, and we have three. good
        #
        #         9: expects 1 >=, and we have 1. good

        # in this way we don't track exactly what matches

        # in fact, this is an easier way to do the bookkeeping for tracking what we updated and when

        tasks.sort()
        workers.sort()

        T = len(tasks)
        W = len(workers)

        # print(f"{tasks=}\n{workers=}\n{pills=}")

        def possible(k: int) -> bool:
            p = pills
            clean_below = deque() # ascending values
            clean_above = deque(workers[-k:]) # ascending values
            drugged = [] # min heap of drugged workers' strengths >= current task, heap b/c we push out of order potentially
            # print(f"{k=}")
            for t in range(k):
                while clean_above and clean_above[0] < tasks[t]:
                    clean_below.append(clean_above.popleft())

                while clean_below and clean_below[0] + strength < tasks[t]: clean_below.popleft()

                while drugged and drugged[0] < tasks[t]: heappop(drugged)

                pills_needed = max(0, k - t - len(clean_above) - len(drugged)) # FIXED: max w/ 0 so p -= pills_needed doesn't ruin our results

                # print(f"  {tasks[t]=}: {clean_above=}, {clean_below=}, {drugged=}, {pills_needed=}, {p=}")

                if pills_needed > p or pills_needed > len(clean_below): return False

                # we move from clean_below to drugged and append to drugged in order so drugged is always ordered
                p -= pills_needed
                for _ in range(pills_needed):
                    # FIXED: do NOT popleft on clean below because the left, i.e. smallest, is the least flexible promotion
                    #        we want to increase cumulative workers to the right for as many elements as possible; we need to pop right/greatest
                    # drugged.append(clean_below.popleft() + strength)
                    heappush(drugged, clean_below.pop() + strength)

            return True

        lo = 0
        hi = min(W, T)
        while lo < hi:
            k = (lo + hi + 1)//2
            if possible(k):
                lo = k
            else:
                hi = k-1

        return hi
1095