948.bag-of-tokens.md

948. Bag of Tokens

Greedy

There are two greedy strategies:

• We must gain the score with the minimum tokens. (The minimum cost)
• We must exchange the score with the maximum power. (The maximum profit)

Based on those strategies, we can sort the tokens and use two pointers to solve the problem.

fun bagOfTokensScore(tokens: IntArray, initPower: Int): Int {
    tokens.sort()
    var power = initPower
    var score = 0
    var up = 0
    var down = token.size - 1
    var maxScore = 0
    while (up <= down) {
        if (tokens[up] <= power) {
            power -= tokens[up]
            score++
            maxScore = maxOf(maxScore, score)
            up++
        } else if (score > 0) {
            power += tokens[down]
            score--
            down--
        } else {
            break
        }
    }
    return maxScore
}