Add solution for 757 (fishercoder1534#124)

ashmichheda · web-flow · commit 73f3431fab48 · 2020-11-04T06:48:50.000-08:00
* added solution for 757

* added test cases for 757

* updated readme

* update readme
diff --git a/README.md b/README.md
@@ -361,6 +361,7 @@ _If you like this project, please leave me a star._ &#9733;
 |762|[Prime Number of Set Bits in Binary Representation](https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_762.java) |  |Easy|
 |760|[Find Anagram Mappings](https://leetcode.com/problems/find-anagram-mappings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_760.java) |  |Easy| 
 |758|[Bold Words in String](https://leetcode.com/problems/bold-words-in-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_758.java) |  |Easy|
+|757|[Set Intersection Size At Least Two](https://leetcode.com/problems/set-intersection-size-at-least-two/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_757.java) |  |Hard|
 |756|[Pyramid Transition Matrix](https://leetcode.com/problems/pyramid-transition-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_756.java) |  |Medium| Backtracking
 |755|[Pour Water](https://leetcode.com/problems/pour-water/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_755.java) ||Medium| Array
 |754|[Reach a Number](https://leetcode.com/problems/reach-a-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_754.java) ||Medium| Math
diff --git a/src/main/java/com/fishercoder/solutions/_757.java b/src/main/java/com/fishercoder/solutions/_757.java
@@ -0,0 +1,43 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+
+/**
+ * Problem 757: Set Intersection Size At Least Two
+ * An integer interval [a, b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b.
+ * Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has size at least 2.
+ */
+
+/**
+ * Approach: Sort the intervals in the ascending order of end range.
+ * In case if the end range of any 2 intervals match,
+ * sort those intervals based on the descending order of start range
+ * e.g. intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
+ * After sorting, intervals[] becomes = [[1,3], [1,4], [3,5],[2,5]]
+ * The reason for sorting based on descending order of start range is to get minimum possible size of S that intersect with A of atleast size 2
+ */
+public class _757 {
+    public static class Solution{
+        public int intersectionSizeTwo(int[][] intervals) {
+            Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0]: a[1] - b[1]);
+            int count = 0;
+            int startTime = Integer.MIN_VALUE, endTime = Integer.MIN_VALUE;
+
+            for(int interval[] : intervals){
+                if(startTime >= interval[0])
+                    continue;
+                else if(endTime >= interval[0]){
+                    startTime = endTime;
+                    endTime = interval[1];
+                    count += 1;
+                }
+                else{
+                    startTime = interval[1] - 1;
+                    endTime = interval[1];
+                    count += 2;
+                }
+            }
+            return count;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_757Test.java b/src/test/java/com/fishercoder/_757Test.java
@@ -0,0 +1,27 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._757;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _757Test {
+    private static _757.Solution solution;
+    int intervals[][];
+
+    @BeforeClass
+    public static void setup(){
+        solution = new _757.Solution();
+    }
+    @Test
+    public void test1() {
+        intervals = new int [][]{{1,3},{1, 4}, {2,5},{3,5}};
+        assertEquals(3, solution.intersectionSizeTwo(intervals));
+    }
+    @Test
+    public void test2() {
+        intervals = new int [][]{{16,18},{11, 18}, {15,23},{1,16}, {10,16},{6,19}, {18,20}, {7,19}};
+        assertEquals(4, solution.intersectionSizeTwo(intervals));
+    }
+}
