leetcode: 1642. Furthest Building You Can Reach

problem

• https://leetcode.com/problems/furthest-building-you-can-reach/

min heap

• O(N * logL) time
• N: number of buildings
• L: number of ladders
• max heap으로 풀 생각만 했는데, 거꾸로 생각해보는 연습을 많이 해봐야겠다.

class Solution {
    fun furthestBuilding(heights: IntArray, bricks: Int, ladders: Int): Int {
        val size = heights.size
        val queue = PriorityQueue<Int>()
        var leftBricks = bricks
        
        for (i in 1 until size) {
            val height = heights[i] - heights[i - 1]
            // skip condition
            if (height <= 0) continue
            
            queue.add(height)            
            // able to use ladder
            if (queue.size <= ladders) continue
            
            // use bricks
            leftBricks -= queue.poll() 
            // return previous building
            if (leftBricks < 0) return i - 1
        }
        // all buildings are reached
        return size - 1   
    }
}