add 1094

fishercoder1534 · fishercoder1534 · commit 79deb72843c4 · 2022-01-06T15:20:29.000-08:00
diff --git a/README.md b/README.md
@@ -461,6 +461,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1103|[Distribute Candies to People](https://leetcode.com/problems/distribute-candies-to-people/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1103.java) | |Easy|Math|
 |1100|[Find K-Length Substrings With No Repeated Characters](https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1100.java) | |Medium|String, Sliding Window|
 |1099|[Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1099.java) |  [:tv:](https://www.youtube.com/watch?v=2Uq7p7HE0TI)|Easy||
+|1094|[Car Pooling](https://leetcode.com/problems/car-pooling/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1094.java) | |Medium|Array, Sorting, Heap, Simulation, Prefix Sum|
 |1090|[Largest Values From Labels](https://leetcode.com/problems/largest-values-from-labels/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1090.java) | [:tv:](https://youtu.be/E0OkE3G95vU)|Medium|HashTable, Greedy|
 |1091|[Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1091.java) | |Medium|BFS|
 |1089|[Duplicate Zeros](https://leetcode.com/problems/duplicate-zeros/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1089.java) | |Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1094.java b/src/main/java/com/fishercoder/solutions/_1094.java
@@ -0,0 +1,28 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+import java.util.PriorityQueue;
+
+public class _1094 {
+    public static class Solution1 {
+        public boolean carPooling(int[][] trips, int capacity) {
+            Arrays.sort(trips, (a, b) -> a[1] - b[1]);
+            PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
+            for (int[] trip : trips) {
+                int startTime = trip[1];
+                int endTime = trip[2];
+                while (!heap.isEmpty() && heap.peek()[1] <= startTime) {
+                    int[] curr = heap.poll();
+                    capacity += curr[0];
+                }
+                int peopleCnt = trip[0];
+                capacity -= peopleCnt;
+                if (capacity < 0) {
+                    return false;
+                }
+                heap.offer(new int[]{peopleCnt, endTime});
+            }
+            return true;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1094Test.java b/src/test/java/com/fishercoder/_1094Test.java
@@ -0,0 +1,40 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._1094;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1094Test {
+    private static _1094.Solution1 solution1;
+    private static int[][] trips;
+    private static int capacity;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1094.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        trips = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[2,1,5],[3,3,7]");
+        capacity = 4;
+        assertEquals(false, solution1.carPooling(trips, capacity));
+    }
+
+    @Test
+    public void test2() {
+        trips = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[2,1,5],[3,3,7]");
+        capacity = 5;
+        assertEquals(true, solution1.carPooling(trips, capacity));
+    }
+
+    @Test
+    public void test3() {
+        trips = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[7,5,6],[6,7,8],[10,1,6]");
+        capacity = 16;
+        assertEquals(false, solution1.carPooling(trips, capacity));
+    }
+}
