1 files changed, 166 insertions, 0 deletions
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);
+    }
+
+}