Baseline Greedy Approach · Easy O(n log n) · O(1)
A compute cluster hands out GPU tokens to queued jobs: each job states the minimum token strength it will accept, and each token has a fixed strength. A job accepts at most one token, and a token serves at most one job. The scheduler wants to satisfy as many jobs as possible, matching the weakest acceptable token to each waiting job.
Input: Two integer arrays: g (each job's minimum acceptable strength) and s (each token's strength).
Output: Return the maximum number of jobs that can be satisfied.
1 <= g.length, s.length <= 2 * 10^41 <= g[i], s[j] <= 2^31 - 1Input: {"g":[1,2,3],"s":[1,1]}
Output: 1
Both tokens are strength 1, so only the greediest-of-three's weakest demand can be met.
Input: {"g":[1,2],"s":[1,2,3]}
Output: 2
Tokens 1 and 2 cover both jobs; the spare token sits unused.