From 68cad41492dc546c7f9a5459c991892d5b01abca Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 22 Sep 2018 14:54:42 -0500
Subject: Check in for my Wisconsin marathon trip

---
 .../sources/CoveringSegments.java                  | 86 ++++++++++++++++++++++
 .../tests/CoveringSegmentsTest.java                | 48 ++++++++++++
 2 files changed, 134 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java

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);
+	}
+
+}
-- 
cgit v1.2.3