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.
1#include <iostream>
2#include <queue>
3#include <vector>
4using namespace std;
5
6int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
7 priority_queue<int, vector<int>, greater<int>> minHeap;
8 for (int i = 0; i < heights.size() - 1; ++i) {
9 int diff = heights[i + 1] - heights[i];
10 if (diff > 0) {
11 minHeap.push(diff);
12 if (minHeap.size() > ladders) {
13 bricks -= minHeap.top();
14 minHeap.pop();
15 if (bricks < 0) return i;
16 }
17 }
18 }
19 return heights.size() - 1;
20}
21
22int main() {
23 vector<int> heights = {4, 12, 2, 7, 3, 18, 20, 3, 19};
24 cout << furthestBuilding(heights, 10, 2) << endl; // Output: 7
25}
26This C++ solution implements a priority queue (or min-heap) to effectively manage the use of bricks and ladders. It pushes positive height differences onto the heap and tries to use ladders first by keeping the size of the heap as the count of ladders. When this count exceeds, it compensates using bricks for the smallest value in the heap.
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.
1function canReach(heights, bricks, ladders, target) {
2 const minHeap = [];
3 function heapPush(val) {
4 minHeap.push(val);
5 minHeap.sort((a, b) => a - b);
6 }
7 function heapPop() {
8 return minHeap.shift();
9 }
10 for (let i = 0; i < target; i++) {
11 let diff = heights[i + 1] - heights[i];
12 if (diff > 0) {
13 heapPush(diff);
14 if (minHeap.length > ladders) {
15 bricks -= heapPop();
16 if (bricks < 0) return false;
17 }
18 }
19 }
20 return true;
21}
22
23function furthestBuilding(heights, bricks, ladders) {
24 let low = 0, high = heights.length - 1;
25 let result = 0;
26 while (low <= high) {
27 let mid = Math.floor((low + high) / 2);
28 if (canReach(heights, bricks, ladders, mid)) {
29 result = mid;
30 low = mid + 1;
31 } else {
32 high = mid - 1;
33 }
34 }
35 return result;
36}
37
38// Example usage
39console.log(furthestBuilding([4, 12, 2, 7, 3, 18, 20, 3, 19], 10, 2)); // Output: 7
40For the JavaScript version, binary searching extends along building indices up with long strides. A helper canReach functions through sorted climbs to offer minimally invasive actions akin to other language principles, discerning extreme outreach via mapping possible corridors.