aboutsummaryrefslogtreecommitdiff
path: root/furthest_building_reach.py
blob: 7fb2a81ca8081851615fa1d8e5af044e38a80ed4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 1642. Furthest Building You Can Reach
import heapq

"""
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 height of
next building, 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
"""


class Solution(object):
    def furthestBuilding(self, heights, bricks, ladders):
        heap = []
        for i in range(len(heights) - 1):
            d = heights[i + 1] - heights[i]
            if d > 0:
                heapq.heappush(heap, d)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)
            if bricks < 0:
                return i
        return len(heights) - 1


if __name__ == "__main__":
    obj = Solution()
    print(obj.furthestBuilding([4, 2, 7, 6, 9, 14, 12], 5, 1))  # expect: 4
    print(obj.furthestBuilding([4, 12, 2, 7, 3, 18, 20, 3, 19], 10, 2))  # expect: 7
    print(obj.furthestBuilding([14, 3, 19, 3], 17, 0))  # expect: 3