aboutsummaryrefslogtreecommitdiff
path: root/furthest_building_reach.c
blob: f5ee496e5a50e8cf38c5ac29dcf95994bc18894f (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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 1642. Furthest Building You Can Reach
#include <stdio.h>
#include <stdlib.h>

/*
 * 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
 */

int heap[100000], heap_cnt;

void insert(int val) {
  int now = heap_cnt;
  heap[now] = val;
  heap_cnt++;
  while (now >= 1) {
    int p = (now - 1) / 2;
    if (heap[now] < heap[p]) {
      int tmp = heap[now];
      heap[now] = heap[p];
      heap[p] = tmp;
      now = p;
    } else
      break;
  }
}

int pop() {
  int res = heap[0], now = 0;
  heap[0] = heap[--heap_cnt];
  while (now * 2 + 1 < heap_cnt) {
    int tmp, next_pos = now;
    if (heap[now] > heap[now * 2 + 1])
      next_pos = now * 2 + 1;
    if (now * 2 + 2 < heap_cnt && heap[next_pos] > heap[now * 2 + 2])
      next_pos = now * 2 + 2;
    if (now == next_pos)
      break;
    tmp = heap[now];
    heap[now] = heap[next_pos];
    heap[next_pos] = tmp;
    now = next_pos;
  }
  return res;
}

int furthestBuilding(int *heights, int heights_size, int bricks, int ladders) {
  int cnt = 0;
  heap_cnt = 0;
  for (int i = 0; i < heights_size - 1; i++) {
    if (heights[i] > heights[i + 1])
      continue;
    insert(heights[i + 1] - heights[i]);
    if (cnt < ladders)
      cnt++;
    else {
      int min = pop();
      if (min > bricks)
        return i;
      bricks -= min;
    }
  }
  return heights_size - 1;
}

int main() {
  int h1[] = {4, 2, 7, 6, 9, 14, 12}, h2[] = {4, 12, 2, 7, 3, 18, 20, 3, 19},
      h3[] = {14, 3, 19, 3};
  printf("%d\n", furthestBuilding(h1, 7, 5, 1));  // expect: 4
  printf("%d\n", furthestBuilding(h2, 9, 10, 2)); // expect: 7
  printf("%d\n", furthestBuilding(h3, 4, 17, 0)); // expect: 3
}