Add line sweep algorithm (TheAlgorithms#4157)

Ltwo3five · web-flow · commit 1551b8f50ba4 · 2023-04-19T08:12:30.000Z
diff --git a/src/main/java/com/thealgorithms/others/LineSweep.java b/src/main/java/com/thealgorithms/others/LineSweep.java
@@ -0,0 +1,51 @@
+package com.thealgorithms.others;
+import java.util.Arrays;
+import java.util.Comparator;
+
+/* Line Sweep algorithm can be used to solve range problems by first sorting the list of ranges
+ * by the start value of the range in non-decreasing order and doing a "sweep" through the number
+ * line(x-axis) by incrementing the start point by 1 and decrementing the end point+1 by 1 on the
+ * number line.
+ * An overlapping range is defined as (StartA <= EndB) AND (EndA >= StartB)
+ * References
+ * https://en.wikipedia.org/wiki/Sweep_line_algorithm
+ * https://en.wikipedia.org/wiki/De_Morgan%27s_laws>
+ */
+public class LineSweep {
+
+    /**  Find Maximum end point
+     *   param = ranges : Array of range[start,end]
+     *   return Maximum Endpoint
+     */
+    public static int FindMaximumEndPoint (int[][]ranges){
+         Arrays.sort(ranges, Comparator.comparingInt(a->a[1]));
+         return ranges[ranges.length-1][1];
+     }
+
+    /**  Find if any ranges overlap
+     *   param = ranges : Array of range[start,end]
+     *   return true if overlap exists false otherwise.
+     */
+    public static boolean isOverlap(int[][] ranges) {
+
+        int maximumEndPoint = FindMaximumEndPoint(ranges);
+        Arrays.sort(ranges, Comparator.comparingInt(a->a[0]));
+        int[] numberLine = new int[maximumEndPoint+2];
+        for (int[] range : ranges) {
+
+            int start = range[0];
+            int end = range[1];
+
+            numberLine[start] += 1;
+            numberLine[end+1] -= 1;
+        }
+
+        int current = 0;
+        int overlaps = 0;
+        for (int num : numberLine) {
+            current += num;
+            overlaps = Math.max(overlaps, current);
+        }
+        return overlaps >1 ;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/others/LineSweepTest.java b/src/test/java/com/thealgorithms/others/LineSweepTest.java
@@ -0,0 +1,29 @@
+package com.thealgorithms.others;
+import static org.junit.jupiter.api.Assertions.*;
+import org.junit.jupiter.api.Test;
+public class LineSweepTest {
+
+
+    @Test
+    void testForOverlap(){
+        int[][]arr = {{0,10},{7,20},{15,24}};
+        assertTrue(LineSweep.isOverlap(arr));
+    }
+
+    @Test
+    void testForNoOverlap(){
+        int[][]arr = {{0,10},{11,20},{21,24}};
+        assertFalse(LineSweep.isOverlap(arr));
+    }
+    @Test
+    void testForOverlapWhenEndAEqualsStartBAndViceVersa(){
+        int[][]arr = {{0,10},{10,20},{21,24}};
+        assertTrue(LineSweep.isOverlap(arr));
+    }
+    @Test
+    void testForMaximumEndPoint(){
+        int[][]arr = {{10,20},{1,100},{14,16},{1,8}};
+        assertEquals(100,LineSweep.FindMaximumEndPoint(arr));
+    }
+
+}
