948.bag-of-tokens.md

948. Bag of Tokens

Greedy

There are two greedy strategies:

• We must gain the score with the minimum tokens if we have enough power. (The minimum cost) So we start from the left.
• We must exchange the score with the maximum power if we don't have enough power. (The maximum profit) So we start from the right.

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 left = 0
    var right = tokens.size - 1
    var score = 0
    var maxScore = 0
    var power = initPower
    while (left <= right) {
        if (tokens[left] <= power) {
            power -= tokens[left]
            score++
            left++
            maxScore = maxOf(maxScore, score)
        } else if (1 <= score) {
            power += tokens[right]
            score--
            right--
        } else {
            break
        }
    }
    return maxScore
}