summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-09-22 14:54:42 -0500
committerHaidong Ji2018-09-22 14:54:42 -0500
commit68cad41492dc546c7f9a5459c991892d5b01abca (patch)
treed98356828d07524e0523d179c7bd8ddfef3975f1
parentaa32f7835fa2776e29fb42c3bdac06ab1f489d0f (diff)
Check in for my Wisconsin marathon trip
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java86
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java48
2 files changed, 134 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
new file mode 100644
index 0000000..db92e1f
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
@@ -0,0 +1,86 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Objects;
+import java.util.Scanner;
+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 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 = scanner.nextInt();
+ Set<Segment> segments = new HashSet<Segment>();
+ for (int i = 0; i < n; i++) {
+ int start, end;
+ start = scanner.nextInt();
+ end = scanner.nextInt();
+ segments.add(new Segment(start, end));
+ }
+ Segment[] s = segments.stream().toArray(Segment[]::new);
+ Arrays.sort(s);
+ Integer[] points = getOptimalPoints(s);
+ System.out.println(points.length);
+ for (int point : points) {
+ System.out.print(point + " ");
+ }
+ }
+ public static Integer[] getOptimalPoints(Segment[] s) {
+ int index = 0;
+ List<Integer> points = new ArrayList<Integer>();
+ while (index < s.length) {
+ points.add(s[index].end);
+ index++;
+ int temp = (int) points.get(points.size()-1);
+ while (index < s.length && s[index].start <= temp) {
+ if (s[index].end < temp)
+ points.set(points.size()-1, s[index].end);
+ index++;
+ }
+ }
+ Integer[] results = new Integer[points.size()];
+ results = points.toArray(results);
+ return results;
+ }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java b/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
new file mode 100644
index 0000000..2f25158
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
@@ -0,0 +1,48 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.junit.jupiter.api.Test;
+
+class CoveringSegmentsTest {
+
+ @Test
+ void testSegment() {
+ CoveringSegments.Segment s = new CoveringSegments.Segment(1, 2);
+ assertEquals(s.start, 1);
+ }
+
+ @Test
+ void testSegmentArray() {
+ CoveringSegments.Segment[] s = new CoveringSegments.Segment[2];
+ s[0] = new CoveringSegments.Segment(3, 4);
+ s[1] = new CoveringSegments.Segment(1, 2);
+ Arrays.sort(s);
+ assertEquals(1, s[0].start);
+ }
+
+ @Test
+ void testSegmentArrayRemoveDups() {
+ CoveringSegments.Segment[] s = new CoveringSegments.Segment[3];
+ s[0] = new CoveringSegments.Segment(3, 4);
+ s[1] = new CoveringSegments.Segment(1, 2);
+ s[2] = new CoveringSegments.Segment(1, 2);
+ Arrays.sort(s);
+ Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>(Arrays.asList(s));
+ assertEquals(2, set.size());
+ }
+
+ @Test
+ void testGetOptimalPoints() {
+ Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+ set.add(new CoveringSegments.Segment(1, 3));
+ set.add(new CoveringSegments.Segment(2, 5));
+ set.add(new CoveringSegments.Segment(3, 6));
+ CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+ Arrays.sort(s);
+ assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
+ }
+
+}