diff options
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)); + } + +} |