Repository: TheAlgorithms/Java
Pull request #4157 (2023-04-18 13:18:34)

line sweep algorithm for range problems
<!-- For completed items, change [ ] to [x] -->

- [ ] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [ ] This pull request is all my own work -- I have not plagiarized it.
- [ ] All filenames are in PascalCase.
- [ ] All functions and variable names follow Java naming conventions.
- [ ] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


LOne2three: I made a new pull request with a new branch as I want to reset my master to the upstream master

Patch:
diff --git a/src/main/java/com/thealgorithms/others/LineSweep.java b/src/main/java/com/thealgorithms/others/LineSweep.java
new file mode 100644
index 00000000..f9db1f74
--- /dev/null
+++ 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 ;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/others/LineSweepTest.java b/src/test/java/com/thealgorithms/others/LineSweepTest.java
new file mode 100644
index 00000000..428556d4
--- /dev/null
+++ 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));
+    }
+
+}