Organizing lottery done!

Pretty challenging and fun exercise. Once again, persistence is the key.
Don't give up, and it is a lot of fun.

3 files changed, 294 insertions, 53 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
index 8cad411..9bf1af5 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
@@ -8,46 +8,47 @@ import java.util.Set;
 
 public class CoveringSegments {
 
-	public static class Segment implements Comparable<Segment> {
-		int start, end;
-		Segment(int start, int end){
-			this.start = start;
-			this.end = end;
-		}
+    public static class Segment implements Comparable<Segment> {
+        int start, end;
 
-		public int compareTo(Segment that) {
-			if (this.start > that.start)
-				return 1;
-			if (this.start == that.start) {
-				if (this.end > that.end)
-					return 1;
-				else
-					if (this.end == that.end) {
-						return 0;
-					}
-					else
-						return -1;
-			}
-			return -1;
-		}
-		
-		@Override
-		public boolean equals(Object o) {
-			if (o==this) return true;
-			if (!(o instanceof Segment)) {
-				return false;
-			}
-			Segment s = (Segment) o;
-			return start==s.start && end == s.end;
-		}
-		
-		@Override
-		public int hashCode() {
-			return Objects.hash(start, end);
-		}
+        Segment(int start, int end) {
+            this.start = start;
+            this.end = end;
+        }
+
+        public int compareTo(Segment that) {
+            if (this.start > that.start)
+                return 1;
+            if (this.start == that.start) {
+                if (this.end > that.end)
+                    return 1;
+                else if (this.end == that.end) {
+                    return 0;
+                } else
+                    return -1;
+            }
+            return -1;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (o == this)
+                return true;
+            if (!(o instanceof Segment)) {
+                return false;
+            }
+            Segment s = (Segment) o;
+            return start == s.start && end == s.end;
+        }
 
-	}
-	public static void main(String[] args) {
+        @Override
+        public int hashCode() {
+            return Objects.hash(start, end);
+        }
+
+    }
+
+    public static void main(String[] args) {
 //        Scanner scanner = new Scanner(System.in);
 //        int n = scanner.nextInt();
 //        Set<Segment> segments = new HashSet<Segment>();
@@ -81,20 +82,21 @@ public class CoveringSegments {
         for (int point : points) {
             System.out.print(point + " ");
         }
-	}
-	public static int[] getOptimalPoints(Segment[] s) {
-		int index = 0;
-		List<Integer> points = new ArrayList<Integer>();
-		while (index < s.length) {
-			points.add(s[index].end);
-			index = index + 1;
-			while (index < s.length && s[index].start <= points.get(points.size()-1).intValue()) {
-				if (s[index].end < points.get(points.size()-1).intValue())
-						points.set(points.size()-1, s[index].end);
-				index = index + 1;
-			}
-		}
-		return points.stream().mapToInt(i -> i).toArray();
-	}
+    }
+
+    public static int[] getOptimalPoints(Segment[] s) {
+        int index = 0;
+        List<Integer> points = new ArrayList<Integer>();
+        while (index < s.length) {
+            points.add(s[index].end);
+            index = index + 1;
+            while (index < s.length && s[index].start <= points.get(points.size() - 1).intValue()) {
+                if (s[index].end < points.get(points.size() - 1).intValue())
+                    points.set(points.size() - 1, s[index].end);
+                index = index + 1;
+            }
+        }
+        return points.stream().mapToInt(i -> i).toArray();
+    }
 
 }
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/PointsAndSegments.java b/AlgoDesignAndTechniqueEdxJava/sources/PointsAndSegments.java
new file mode 100644
index 0000000..bc20b4b
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/PointsAndSegments.java
@@ -0,0 +1,166 @@
+import java.util.Arrays;
+import java.util.Objects;
+import java.util.Scanner;
+
+public class PointsAndSegments {
+
+    public static class Segment implements Comparable<Segment> {
+        int start, end;
+
+        Segment(int start, int end) {
+            this.start = start;
+            this.end = end;
+        }
+
+        public int compareTo(Segment that) {
+            if (this.start > that.start)
+                return 1;
+            if (this.start == that.start) {
+                if (this.end > that.end)
+                    return 1;
+                else if (this.end == that.end) {
+                    return 0;
+                } else
+                    return -1;
+            }
+            return -1;
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (o == this)
+                return true;
+            if (!(o instanceof Segment)) {
+                return false;
+            }
+            Segment s = (Segment) o;
+            return start == s.start && end == s.end;
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hash(start, end);
+        }
+
+    }
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n, m;
+        n = scanner.nextInt();
+        m = scanner.nextInt();
+        int[] starts = new int[n];
+        int[] ends = new int[n];
+        int[] points = new int[m];
+        for (int i = 0; i < n; i++) {
+            starts[i] = scanner.nextInt();
+            ends[i] = scanner.nextInt();
+        }
+        for (int i = 0; i < m; i++) {
+            points[i] = scanner.nextInt();
+        }
+        // use fastCountSegments
+        int[] cnt = fastestCountSegments(starts, ends, points);
+        for (int x : cnt) {
+            System.out.print(x + " ");
+        }
+    }
+
+    public static int[] naiveCountSegments(int[] starts, int[] ends, int[] points) {
+        int[] cnt = new int[points.length];
+        for (int i = 0; i < points.length; i++) {
+            for (int j = 0; j < starts.length; j++) {
+                if (starts[j] <= points[i] && points[i] <= ends[j]) {
+                    cnt[i]++;
+                }
+            }
+        }
+        return cnt;
+    }
+
+    public static int[] fastCountSegments(int[] starts, int[] ends, int[] points) {
+        Segment[] s = new Segment[starts.length];
+        for (int i = 0; i < s.length; i++) {
+            s[i] = new Segment(starts[i], ends[i]);
+        }
+        Arrays.sort(s);
+        int[] results = new int[points.length];
+        for (int i = 0; i < results.length; i++) {
+            results[i] = segCounts(s, points[i], 0, s.length - 1);
+        }
+        return results;
+    }
+
+    public static int[] fasterCountSegments(int[] starts, int[] ends, int[] points) {
+        Segment[] s = new Segment[starts.length];
+        Segment[] p = new Segment[points.length];
+        for (int i = 0; i < s.length; i++) {
+            s[i] = new Segment(starts[i], ends[i]);
+        }
+        for (int i = 0; i < p.length; i++) {
+            p[i] = new Segment(points[i], i);
+        }
+        Arrays.sort(s);
+        Arrays.sort(p);
+        int[] results = new int[points.length];
+        int r = segCounts(s, p[0].start, 0, s.length - 1);
+        results[p[0].end] = r;
+        for (int i = 1; i < results.length; i++) {
+            if (p[i].start == p[i - 1].start)
+                results[p[i].end] = results[p[i - 1].end];
+            else
+                results[p[i].end] = segCounts(s, p[i].start, 0, s.length - 1);
+        }
+        return results;
+    }
+
+    public static int[] fastestCountSegments(int[] starts, int[] ends, int[] points) {
+        // Implement algo described here, really clever:
+        // https://www.coursera.org/learn/algorithmic-toolbox/discussions/all/threads/QJ1jK9wNEeWdPBL2iFTrAw/replies/Ihiw4txhEeWK5g7mfcS2Xw/comments/oyAMaeIiEeWyqwpvChh66Q
+        // l->1, p->2, r->3 for Segment.end property
+        Segment[] s = new Segment[starts.length + ends.length + points.length];
+        Segment[] p = new Segment[points.length];
+        for (int i = 0; i < p.length; i++) {
+            p[i] = new Segment(points[i], i);
+            s[2 * starts.length + i] = new Segment(points[i], 2);
+        }
+        for (int i = 0; i < starts.length; i++) {
+            s[i] = new Segment(starts[i], 1);
+            s[i + starts.length] = new Segment(ends[i], 3);
+        }
+        Arrays.sort(s);
+        Arrays.sort(p);
+        int[] results = new int[points.length];
+        int count = 0;
+        int j = 0;
+        for (int i = 0; i < s.length; i++) {
+            if (s[i].end == 1) {
+                count = count + 1;
+            }
+            if (s[i].end == 2) {
+                results[j] = count;
+                j = j + 1;
+            }
+            if (s[i].end == 3) {
+                count = count - 1;
+            }
+        }
+        int[] finalResults = new int[points.length];
+        for (int i = 0; i < finalResults.length; i++) {
+           finalResults[p[i].end] = results[i]; 
+        }
+        return finalResults;
+    }
+
+    public static int segCounts(Segment[] s, int p, int low, int high) {
+        if (high < low)
+            return 0;
+        int mid = low + (high - low) / 2;
+        if (p < s[mid].start)
+            return segCounts(s, p, low, mid - 1);
+        if (p > s[mid].end)
+            return segCounts(s, p, mid + 1, high);
+        return 1 + segCounts(s, p, low, mid - 1) + segCounts(s, p, mid + 1, high);
+    }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/PointsAndSegmentsTest.java b/AlgoDesignAndTechniqueEdxJava/tests/PointsAndSegmentsTest.java
new file mode 100644
index 0000000..6d56ed2
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/PointsAndSegmentsTest.java
@@ -0,0 +1,73 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.Arrays;
+
+import org.junit.jupiter.api.Test;
+
+class PointsAndSegmentsTest {
+
+    @Test
+    void test() {
+        int[] starts = {0, 7};
+        int[] ends = {5, 10};
+        int[] points = {1, 6, 11};
+        int[] results = {1, 0, 0};
+        assertArrayEquals(results, PointsAndSegments.naiveCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fasterCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fastestCountSegments(starts, ends, points));
+    }
+
+    @Test
+    void test1() {
+        int[] starts = {-10};
+        int[] ends = {10};
+        int[] points = {-100, 100, 0};
+        int[] results = {0, 0, 1};
+        assertArrayEquals(results, PointsAndSegments.naiveCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fasterCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fastestCountSegments(starts, ends, points));
+    }
+
+    @Test
+    void test2() {
+        int[] starts = {0, -3, 7};
+        int[] ends = {5, 2, 10};
+        int[] points = {1, 6};
+        int[] results = {2, 0};
+        assertArrayEquals(results, PointsAndSegments.naiveCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fasterCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fastestCountSegments(starts, ends, points));
+    }
+
+    @Test
+    void test3() {
+        int[] starts = {0, 7};
+        int[] ends = {5, 10};
+        int[] points = {1, 6, 11};
+        int[] results = {1, 0, 0};
+        assertArrayEquals(results, PointsAndSegments.fasterCountSegments(starts, ends, points));
+        assertArrayEquals(results, PointsAndSegments.fastestCountSegments(starts, ends, points));
+    }
+
+    @Test
+    void test4() {
+        PointsAndSegments.Segment[] s = new PointsAndSegments.Segment[3];
+        s[0] = new PointsAndSegments.Segment(0, 5);
+        s[1] = new PointsAndSegments.Segment(-3, 2);
+        s[2] = new PointsAndSegments.Segment(7, 10);
+        int p = 1;
+        assertEquals(2, PointsAndSegments.segCounts(s, p, 0, s.length - 1));
+    }
+
+    @Test
+    void test5() {
+        PointsAndSegments.Segment[] s = new PointsAndSegments.Segment[3];
+        s[0] = new PointsAndSegments.Segment(0, 5);
+        s[1] = new PointsAndSegments.Segment(-3, 2);
+        s[2] = new PointsAndSegments.Segment(7, 10);
+        int p = 6;
+        Arrays.sort(s);
+        assertEquals(0, PointsAndSegments.segCounts(s, p, 0, s.length - 1));
+    }
+
+}