add 881

fishercoder1534 · fishercoder1534 · commit 12961cded7a0 · 2021-01-14T07:42:09.000-08:00
diff --git a/README.md b/README.md
@@ -362,6 +362,7 @@ _If you like this project, please leave me a star._ &#9733;
 |885|[Spiral Matrix III](https://leetcode.com/problems/spiral-matrix-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_885.java)  |[:tv:](https://www.youtube.com/watch?v=0qep3f9cqVs) |Medium|
 |884|[Uncommon Words from Two Sentences](https://leetcode.com/problems/uncommon-words-from-two-sentences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_884.java) | |Easy|
 |883|[Projection Area of 3D Shapes](https://leetcode.com/problems/projection-area-of-3d-shapes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_883.java) | |Easy|Math
+|881|[Boats to Save People](https://leetcode.com/problems/boats-to-save-people/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_881.java) | |Medium|Two Pointers, Greedy
 |880|[Decoded String at Index](https://leetcode.com/problems/decoded-string-at-index/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_880.java) | |Medium|Stack
 |876|[Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_876.java) | |Easy|
 |872|[Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_872.java) |  |Easy| DFS, recursion
diff --git a/src/main/java/com/fishercoder/solutions/_881.java b/src/main/java/com/fishercoder/solutions/_881.java
@@ -0,0 +1,60 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.TreeMap;
+
+public class _881 {
+    public static class Solution1 {
+        public int numRescueBoats(int[] people, int limit) {
+            TreeMap<Integer, Integer> map = new TreeMap<>();
+            for (int w : people) {
+                map.put(w, map.getOrDefault(w, 0) + 1);
+            }
+            int boats = 0;
+            List<Integer> uniqWeights = new ArrayList(map.keySet());
+            int left = 0;
+            int right = uniqWeights.size() - 1;
+            while (left < right) {
+                int heavierWeight = uniqWeights.get(right);
+                int lighterWeight = uniqWeights.get(left);
+                if (heavierWeight + lighterWeight <= limit) {
+                    int pairs = Math.min(map.get(heavierWeight), map.get(lighterWeight));
+                    boats += pairs;
+                    if (map.get(heavierWeight) == pairs && map.get(lighterWeight) == pairs) {
+                        map.remove(heavierWeight);
+                        map.remove(lighterWeight);
+                        left++;
+                        right--;
+                    } else if (map.get(heavierWeight) == pairs) {
+                        map.remove(heavierWeight);
+                        map.put(lighterWeight, map.get(lighterWeight) - pairs);
+                        right--;
+                    } else {
+                        map.remove(lighterWeight);
+                        map.put(heavierWeight, map.get(heavierWeight) - pairs);
+                        left++;
+                    }
+                } else {
+                    boats += map.get(heavierWeight);
+                    map.remove(heavierWeight);
+                    right--;
+                }
+            }
+            if (!map.isEmpty()) {
+                int weight = uniqWeights.get(left);
+                int remainingPeople = map.get(weight);
+                if (remainingPeople == 1) {
+                    boats++;
+                } else {
+                    if (weight * 2 <= limit) {
+                        boats += (remainingPeople / 2 + ((remainingPeople % 2 == 0) ? 0 : 1));
+                    } else {
+                        boats += remainingPeople;
+                    }
+                }
+            }
+            return boats;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_881Test.java b/src/test/java/com/fishercoder/_881Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._881;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _881Test {
+    private static _881.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _881.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(1, solution1.numRescueBoats(new int[]{1, 2}, 3));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(3, solution1.numRescueBoats(new int[]{3, 2, 2, 1}, 3));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(4, solution1.numRescueBoats(new int[]{3, 5, 3, 4}, 5));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(2, solution1.numRescueBoats(new int[]{2, 4}, 5));
+    }
+
+    @Test
+    public void test5() {
+        assertEquals(29, solution1.numRescueBoats(new int[]{4, 9, 3, 1, 1, 7, 6, 10, 10, 10, 1, 8, 8, 7, 8, 10, 7, 4, 6, 3, 6, 1, 2, 4, 8, 8, 4, 7, 1, 2, 10, 3, 4, 6, 3, 5, 3, 1, 2, 6, 1, 5, 4, 5, 1, 10, 5, 9, 10, 4}, 10));
+    }
+
+}
