add 1642

fishercoder1534 · fishercoder1534 · commit d376196fa4b0 · 2021-04-26T08:03:12.000-07:00
diff --git a/README.md b/README.md
@@ -97,6 +97,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1656|[Design an Ordered Stream](https://leetcode.com/problems/design-an-ordered-stream/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1656.java) ||Easy|Array, Design|
 |1652|[Defuse the Bomb](https://leetcode.com/problems/defuse-the-bomb/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1652.java) ||Easy|Array|
 |1646|[Get Maximum in Generated Array](https://leetcode.com/problems/get-maximum-in-generated-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1646.java) ||Easy|Array|
+|1642|[Furthest Building You Can Reach](https://leetcode.com/problems/furthest-building-you-can-reach/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1642.java) ||Medium|Binary Search, Heap|
 |1641|[Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1641.java) |[:tv:](https://youtu.be/gdH4yfgfwiU)|Medium|Math, DP, Backtracking|
 |1640|[Check Array Formation Through Concatenation](https://leetcode.com/problems/check-array-formation-through-concatenation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1640.java) ||Easy|Array, Sort|
 |1637|[Widest Vertical Area Between Two Points Containing No Points](https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points/)|[Javascript](./javascript/_1637.js)| | Medium | Sort |
diff --git a/src/main/java/com/fishercoder/solutions/_1642.java b/src/main/java/com/fishercoder/solutions/_1642.java
@@ -0,0 +1,37 @@
+package com.fishercoder.solutions;
+
+import java.util.PriorityQueue;
+
+public class _1642 {
+    public static class Solution1 {
+        public int furthestBuilding(int[] heights, int bricks, int ladders) {
+            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+            int i = 0;
+            //we'll assume to use ladders for the first l jumps and adjust it afterwards
+            for (; i < heights.length - 1 && minHeap.size() < ladders; i++) {
+                int diff = heights[i + 1] - heights[i];
+                if (diff > 0) {
+                    minHeap.offer(diff);
+                }
+            }
+            //now ladders have been used up, we'll use bricks to jump
+            while (i < heights.length - 1) {
+                int diff = heights[i + 1] - heights[i];
+                if (diff > 0) {
+                    //we'll check if the last one that cost a ladder could actually be filled with some bricks
+                    if (!minHeap.isEmpty() && minHeap.peek() < diff) {
+                        bricks -= minHeap.poll();
+                        minHeap.offer(diff);
+                    } else {
+                        bricks -= diff;
+                    }
+                    if (bricks < 0) {
+                        return i;
+                    }
+                }
+                i++;
+            }
+            return i;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1642Test.java b/src/test/java/com/fishercoder/_1642Test.java
@@ -0,0 +1,47 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1642;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1642Test {
+    private static _1642.Solution1 solution1;
+
+    @BeforeClass
+    public static void setUp() {
+        solution1 = new _1642.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(4, solution1.furthestBuilding(new int[]{4, 2, 7, 6, 9, 14, 12}, 5, 1));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(7, solution1.furthestBuilding(new int[]{4, 12, 2, 7, 3, 18, 20, 3, 19}, 10, 2));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(3, solution1.furthestBuilding(new int[]{14, 3, 19, 3}, 17, 0));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(6, solution1.furthestBuilding(new int[]{17, 16, 5, 10, 10, 14, 7}, 74, 6));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals(1, solution1.furthestBuilding(new int[]{7, 5, 13}, 0, 0));
+    }
+
+    @Test
+    public void test6() {
+        assertEquals(3, solution1.furthestBuilding(new int[]{2, 7, 9, 12}, 5, 1));
+    }
+
+}
