This approach uses a greedy strategy combined with a max-heap (priority queue) to determine the optimal use of bricks and ladders. The idea is to always use bricks first for the smallest height difference and use ladders for the largest, potentially reserving the ladders for future taller buildings. Whenever we encounter a new jump (difference in height), we add it to the heap, and if the total number of jumps exceeds the available ladders, we use bricks for the smallest jump. If we don’t have enough bricks, we can’t proceed further.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing height differences.
1import heapq
2
3def furthest_building(heights, bricks, ladders):
4 min_heap = []
5 for i in range(len(heights) - 1):
6 diff = heights[i + 1] - heights[i]
7 if diff > 0:
8 heapq.heappush(min_heap, diff)
9 if len(min_heap) > ladders:
10 bricks -= heapq.heappop(min_heap)
11 if bricks < 0:
12 return i
13 return len(heights) - 1
14
15# Sample run
16heights = [4, 2, 7, 6, 9, 14, 12]
17print(furthest_building(heights, 5, 1)) # Output: 4
18This Python solution efficiently uses a min-heap to optimize the allocation of ladders and bricks. By storing the smallest height differences, it ensures that the smallest climbs are covered by bricks once ladders run out, similar to priority queue usage in other language solutions.
This approach employs binary search to find the furthest building we can reach. The binary search is performed over the indices of the buildings (0 to n-1). For each index midpoint in the search, we check if it's possible to reach that building, given the constraints of available bricks and ladders using a helper function that checks feasibility by simulating resource allocation greedily. The search continually refines the possible maximum index based on resource ability.
Time Complexity: O(n log n) because of binary search with operations similar to heap for each midpoint.
Space Complexity: O(n) to store the min-heap simulation for each search step.
1#include <stdio.h>
2#include <stdlib.h>
3
4int canReach(int* heights, int heightsSize, int bricks, int ladders, int target) {
5 int* minHeap = (int*)malloc(sizeof(int) * heightsSize);
6 int heapSize = 0;
7 for (int i = 0; i < target; ++i) {
8 int diff = heights[i + 1] - heights[i];
9 if (diff > 0) {
10 minHeap[heapSize++] = diff;
11 for (int j = heapSize - 1; j > 0 && minHeap[j] < minHeap[j - 1]; --j) {
12 int temp = minHeap[j];
13 minHeap[j] = minHeap[j - 1];
14 minHeap[j - 1] = temp;
15 }
16 if (heapSize > ladders) {
17 bricks -= minHeap[--heapSize];
18 if (bricks < 0) {
19 free(minHeap);
20 return 0;
21 }
22 }
23 }
24 }
25 free(minHeap);
26 return 1;
27}
28
29int furthestBuilding(int* heights, int heightsSize, int bricks, int ladders) {
30 int low = 0, high = heightsSize - 1, result = 0;
31 while (low <= high) {
32 int mid = (low + high) / 2;
33 if (canReach(heights, heightsSize, bricks, ladders, mid)) {
34 result = mid;
35 low = mid + 1;
36 } else {
37 high = mid - 1;
38 }
39 }
40 return result;
41}
42
43int main() {
44 int heights[] = {4, 2, 7, 6, 9, 14, 12};
45 int result = furthestBuilding(heights, 7, 5, 1);
46 printf("%d\n", result); // Output: 4
47 return 0;
48}
49In this C code, a binary search is conducted over the range of buildings. For each midpoint, a helper function 'canReach' checks the viability of reaching that point by exploiting a simulated min-heap strategy. This allows optimal usage of the available bricks and ladders, guiding the binary search to converge on the maximum reachable building index.