add 986

fishercoder1534 · fishercoder1534 · commit b7d4b8a0fa0c · 2020-02-14T15:13:19.000-08:00
diff --git a/README.md b/README.md
@@ -130,6 +130,7 @@ _If you like this project, please leave me a star._ &#9733;
 |989|[Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_989.java) | |Easy| Array
 |988|[Smallest String Starting From Leaf](https://leetcode.com/problems/smallest-string-starting-from-leaf/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_988.java) | |Medium| Tree, DFS
 |987|[Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_987.java) | |Medium| Recursion
+|986|[Interval List Intersections](https://leetcode.com/problems/interval-list-intersections/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_986.java) | |Medium| Two Pointers
 |985|[Sum of Even Numbers After Queries](https://leetcode.com/problems/sum-of-even-numbers-after-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_985.java) | |Easy| Array
 |979|[Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_979.java) | |Medium| Recursion
 |977|[Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_977.java) | |Easy| Array
diff --git a/src/main/java/com/fishercoder/solutions/_986.java b/src/main/java/com/fishercoder/solutions/_986.java
@@ -0,0 +1,52 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 986. Interval List Intersections
+ *
+ * Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
+ * Return the intersection of these two interval lists.
+ *
+ * (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.
+ * The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.
+ * For example, the intersection of [1, 3] and [2, 4] is [2, 3].)
+ *
+ * Example 1:
+ * Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
+ * Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
+ * Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
+ *
+ * Note:
+ * 0 <= A.length < 1000
+ * 0 <= B.length < 1000
+ * 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
+ * NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
+ * */
+public class _986 {
+    public static class Solution1 {
+        public int[][] intervalIntersection(int[][] A, int[][] B) {
+            int i = 0;
+            int j = 0;
+            List<int[]> list = new ArrayList<>();
+            while (i < A.length && j < B.length) {
+                int start = Math.max(A[i][0], B[j][0]);
+                int end = Math.min(A[i][1], B[j][1]);
+                if (start <= end) {
+                    list.add(new int[]{start, end});
+                }
+                if (end == A[i][1]) {
+                    i++;
+                } else {
+                    j++;
+                }
+            }
+            int[][] result = new int[list.size()][2];
+            for (int k = 0; k < list.size(); k++) {
+                result[k] = list.get(k);
+            }
+            return result;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_986Test.java b/src/test/java/com/fishercoder/_986Test.java
@@ -0,0 +1,49 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._986;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _986Test {
+    private static _986.Solution1 solution1;
+    private static int[][] A;
+    private static int[][] B;
+    private static int[][] expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _986.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        A = new int[][]{
+                {0, 2},
+                {5, 10},
+                {13, 23},
+                {24, 25}
+        };
+        B = new int[][]{
+                {1, 5},
+                {8, 12},
+                {15, 24},
+                {25, 26}
+        };
+        expected = new int[][]{
+                {1, 2},
+                {5, 5},
+                {8, 10},
+                {15, 23},
+                {24, 24},
+                {25, 25}
+        };
+        int[][] actual = solution1.intervalIntersection(A, B);
+        CommonUtils.print2DIntArray(actual);
+        assertEquals(expected, actual);
+    }
+
+
+}
