Today's Challenge

fabichoi 2022. 6. 21. 23:45

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

Furthest Building You Can Reach - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

minheap을 이용한 풀이

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:        
        min_heap = []
        n = len(heights)
        
        for i in range(n-1):
            climb = heights[i+1] - heights[i]
            
            if climb <= 0:
                continue
                
            if climb > 0:
                heapq.heappush(min_heap, climb)
            
            if len(min_heap) > ladders:
                brick_need = heapq.heappop(min_heap)
                bricks -= brick_need
            
            if bricks < 0:
                return i
        
        return n-1