<p>You are given a <strong>0-indexed</strong> integer array <code>players</code>, where <code>players[i]</code> represents the <strong>ability</strong> of the <code>i<sup>th</sup></code> player. You are also given a <strong>0-indexed</strong> integer array <code>trainers</code>, where <code>trainers[j]</code> represents the <strong>training capacity </strong>of the <code>j<sup>th</sup></code> trainer.</p>

<p>The <code>i<sup>th</sup></code> player can <strong>match</strong> with the <code>j<sup>th</sup></code> trainer if the player&#39;s ability is <strong>less than or equal to</strong> the trainer&#39;s training capacity. Additionally, the <code>i<sup>th</sup></code> player can be matched with at most one trainer, and the <code>j<sup>th</sup></code> trainer can be matched with at most one player.</p>

<p>Return <em>the <strong>maximum</strong> number of matchings between </em><code>players</code><em> and </em><code>trainers</code><em> that satisfy these conditions.</em></p>

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

<pre>
<strong>Input:</strong> players = [4,7,9], trainers = [8,2,5,8]
<strong>Output:</strong> 2
<strong>Explanation:</strong>
One of the ways we can form two matchings is as follows:
- players[0] can be matched with trainers[0] since 4 &lt;= 8.
- players[1] can be matched with trainers[3] since 7 &lt;= 8.
It can be proven that 2 is the maximum number of matchings that can be formed.
</pre>

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

<pre>
<strong>Input:</strong> players = [1,1,1], trainers = [10]
<strong>Output:</strong> 1
<strong>Explanation:</strong>
The trainer can be matched with any of the 3 players.
Each player can only be matched with one trainer, so the maximum answer is 1.
</pre>

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

<ul>
	<li><code>1 &lt;= players.length, trainers.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= players[i], trainers[j] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Note:</strong> This question is the same as <a href="https://leetcode.com/problems/assign-cookies/description/" target="_blank"> 445: Assign Cookies.</a></p>


# Submitted by Samy Vilar <samy_vilar> on 09/08/2024

# Apply a greedy approach while merging the ordered lists;
# Essentially for each (ever greater) trainer we will always take the 
# greatest player, among all possible remaining valid 
# (i.e. those that are lesser or equal)

# Given we are only inerested in the size of the matching it would
# suffice to simply keep track of the "number" of valid players
# each subsequent trainer may choose from; as such for each never
# before considered player that is lesser or equal to the current
# trainer we increment some counter;
# o.t.h. should the aforementioned player be greater than we check
# we can increment our solution iff the aforementioned counter is 
# positive, taking care to decrement the counter in said case;
# Since should it be 0, it would imply either no "valid" players at 
# all existed or they where all already "assigned", in either case
# our solution couldn't possibly increase;

# Since we are pre-dominantly bounded by our sorting algorithm given
# at all times we are always "consuming" at least 1 player or trainer
# would imply O(n * log(n)) time w/ O(1) additional-space;

# if we keep track of the remaining trainers, then should at any time
# exhaust all players, then we note our solution we increase by either
# said amount or counter, which ever is lesser;

# version 1.1 simplication based on other submission(s)
#             informally for each player we take the nearest available trainer;
#             NOTE this is essentially the same approach as before i.e. for each 
#             trainer we take the greatest available player as before 

# version 1.2

class Solution:
    def matchPlayersAndTrainers(
        self, players: List[int], trainers: List[int], matched=0, pending=0,
        kind=itemgetter(1), falses=repeat(False), truths=repeat(True)  
    ):
        players.sort()
        trainers.sort()
        for trainers, cnt in groupby(map(kind, merge(zip(players, falses), 
                                                     zip(trainers, truths)))):
            if trainers:
                if pending < (cnt := sum(cnt)):
                    cnt = pending
                matched += cnt
                pending -= cnt
            else:
                pending += sum(map(not_, cnt))
        return matched

            
        # players.sort()
        # player = next(players := iter(players))
        # trainers[:] = filter(player.__le__, trainers)
        # heapify(trainers)        
        # for trainer in map(heappop, repeat(trainers, len(trainers))):
        #     if player <= trainer:                
        #         if not (player := next(players, False)):
        #             return len(players)
        #         matched += 1
        # return matched                
674