前往
大廳
主題

LeetCode - 2410. Maximum Matching of Players With Trainers 解題心得

Not In My Back Yard | 2023-08-07 12:00:15 | 巴幣 0 | 人氣 89

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的整數陣列 players,其中 players[i] 代表著第 i 位玩家的能力值。你同時也被給定一個索引值從 0 開始的整數陣列 trainers,其中 trainers[j] 代表著第 j 位訓練家的訓練能力。

第 i 位玩家可以與第 j 位訓練家相配,則代表玩家的能力值小於等於訓練家的訓練能力。此外,第 i 位玩家最多只能配到一位訓練家,而第 j 位訓練家最多只能配到一位玩家。

回傳可以滿足以上條件的最多可能的玩家與訓練家之配對數。

限制:
1 ≦ players.length, trainers.length ≦ 10 ^ 5
1 ≦ players[i], trainers[j] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: players = [4,7,9], trainers = [8,2,5,8]
輸出: 2
解釋:
其中一個可以形成兩個配對的方式為以下:
- players[0] 可以與 trainers[0] 配對,因為 4 ≦ 8。
- players[1] 可以與 trainers[3] 配對,因為 7 ≦ 8。
可以證明 2 是最多可形成的配對數。

範例 2:
輸入: players = [1,1,1], trainers = [10]
輸出: 1
解釋:
該訓練家可以與 3 位玩家中任一位配對。
每個玩家最多只能與一位訓練家配對,所以最大之答案為 1。
(原意如此,而正確的邏輯應為「一位訓練家最多只能與一位玩家配對」。)


解題思維:
把玩家和訓練家各自按照能力值由小排到大,然後盡量用能力小的玩家去配能力小(但符合題目條件)的訓練家。

可以看到當玩家 i 與訓練家 j 配對後,玩家 i + 1 不可能與訓練家 0 ~ j 配對(要嘛能力太小配不上,要嘛已經跟別人配過了)。所以玩家 i 只要往訓練家 j + 1 方向找即可。

最後便可以知道最多可以湊出幾對。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作