LeetCode 솔루션

[6/21] 1642. Furthest Building You Can Reach

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.06.20 19:14

6,725 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

1642. Furthest Building You Can Reach

Medium

189455Add to ListShare

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length

#Amazon, #Google, #Microsoft, #VMware, #Bloomberg, #Media.net, #Array, #Greedy, #Heap(Priority Queue)

링크

https://leetcode.com/problems/furthest-building-you-can-reach/ 1922 회 연결

익명
작성일 2022.06.21 21:47

import collections, heapq
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        reached = 0
        
        max_heap = [] # bricks_used
        heapq.heapify(max_heap)
        
        for idx, h in enumerate(heights[:-1]):
            if heights[idx+1] <= h: 
                reached+=1
                continue
                
            diff = heights[idx+1] - h
            if bricks < diff:
                if not ladders: break
                
                # ========= Same as Below if statement======
                # if not max_heap or diff > -1*max_heap[0]:
                #     ladders -= 1
                # else:
                #     bricks += -1*heapq.heappop(max_heap)
                #     heapq.heappush(max_heap, -1*diff)
                #     bricks -= diff
                #     ladders -= 1
                # ===============================
                #=============Same as Above if-else
                if max_heap and diff < -1*max_heap[0]:
                    bricks += -1*heapq.heappop(max_heap)
                    heapq.heappush(max_heap, -1*diff)
                    bricks -= diff
                ladders -= 1
                # =================================
            
            else:
                bricks -= diff
                heapq.heappush(max_heap, -1*diff)
            reached += 1
        
        return reached

Runtime: 866 ms, faster than 44.92% of Python3 online submissions for Furthest Building You Can Reach.
Memory Usage: 28.7 MB, less than 16.28% of Python3 online submissions for Furthest Building You Can Reach.
[code=Python 3]import collections, heapq
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        reached = 0
        
        max_heap = [] # bricks_used
        heapq.heapify(max_heap)
        
        for idx, h in enumerate(heights[:-1]):
            if heights[idx+1] <= h: 
                reached+=1
                continue
                
            diff = heights[idx+1] - h
            if bricks < diff:
                if not ladders: break
                
                # ========= Same as Below if statement======
                # if not max_heap or diff > -1*max_heap[0]:
                #     ladders -= 1
                # else:
                #     bricks += -1*heapq.heappop(max_heap)
                #     heapq.heappush(max_heap, -1*diff)
                #     bricks -= diff
                #     ladders -= 1
                # ===============================
                #=============Same as Above if-else
                if max_heap and diff < -1*max_heap[0]:
                    bricks += -1*heapq.heappop(max_heap)
                    heapq.heappush(max_heap, -1*diff)
                    bricks -= diff
                ladders -= 1
                # =================================
            
            else:
                bricks -= diff
                heapq.heappush(max_heap, -1*diff)
            reached += 1
        
        return reached
            
            [/code]