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 <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc(const void *a, const void *b) {
5 return *(int *)b - *(int *)a;
6}
7
8int furthestBuilding(int* heights, int heightsSize, int bricks, int ladders) {
9 int* diffs = (int*)malloc(heightsSize * sizeof(int));
10 int diffSize = 0;
11 for (int i = 0; i < heightsSize - 1; ++i) {
12 int diff = heights[i + 1] - heights[i];
13 if (diff > 0) diffs[diffSize++] = diff;
14 }
15
16 qsort(diffs, diffSize, sizeof(int), cmpfunc);
17 for (int i = 0; i < diffSize && bricks >= 0; ++i) {
18 if (ladders > 0) {
19 ladders--;
20 } else {
21 bricks -= diffs[i];
22 if (bricks < 0) return i;
23 }
24 }
25
26 free(diffs);
27 return heightsSize - 1;
28}
29
30int main() {
31 int heights[] = {4, 2, 7, 6, 9, 14, 12};
32 int result = furthestBuilding(heights, 7, 5, 1);
33 printf("%d\n", result); // Output: 4
34 return 0;
35}
36This C code uses a simple array to store differences between consecutive buildings that require resource expenditure. It sorts these differences in descending order and tries to accommodate the largest jumps with ladders, using bricks for the rest. While sorting and processing the differences, it tracks when there are insufficient bricks to continue, returning the last accessible building index.
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.
1using System;
2using System.Collections.Generic;
3
4public class FurthestBuilding {
5 private static bool CanReach(int[] heights, int bricks, int ladders, int target) {
6 var minHeap = new SortedSet<(int climb, int index)>(Comparer<(int, int)>.Create((x, y) => x.climb == y.climb ? x.index.CompareTo(y.index) : x.climb.CompareTo(y.climb)));
7 for (int i = 0; i < target; i++) {
8 int diff = heights[i + 1] - heights[i];
9 if (diff > 0) {
10 minHeap.Add((diff, i));
11 if (minHeap.Count > ladders) {
12 bricks -= minHeap.Min.climb;
13 minHeap.Remove(minHeap.Min);
14 if (bricks < 0) return false;
15 }
16 }
17 }
18 return true;
19 }
20
21 public static int FurthestBuildingMethod(int[] heights, int bricks, int ladders) {
22 int low = 0, high = heights.Length - 1, result = 0;
23 while (low <= high) {
24 int mid = low + (high - low) / 2;
25 if (CanReach(heights, bricks, ladders, mid)) {
26 result = mid;
27 low = mid + 1;
28 } else {
29 high = mid - 1;
30 }
31 }
32 return result;
33 }
34
35 public static void Main() {
36 int[] heights = { 4, 12, 2, 7, 3, 18, 20, 3, 19 };
37 Console.WriteLine(FurthestBuildingMethod(heights, 10, 2)); // Output: 7
38 }
39}
40This C# binary search-based solution initiates a traversal over building indices moderated by helper function CanReach. Implementing a sorted set acts as a priority scaffolding to rank height differences, ensuring minimal climbs use bricks, thereby revealing probable maximums within the structure.