Covering Segments done!

Pretty challenging and interesting. I'm glad I worked out the algo in
Python first for this problem. Good review of the comparable interface.
Good feeling of stream and lambda functions. Eclipse's erronous
reporting of errors is annoying.

2 files changed, 176 insertions, 14 deletions

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
index db92e1f..8cad411 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
@@ -48,39 +48,53 @@ public class CoveringSegments {
 
 	}
 	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);
+//        int[] points = getOptimalPoints(s);
+//        System.out.println(points.length);
+//        for (int point : points) {
+//            System.out.print(point + " ");
+//        }
         Scanner scanner = new Scanner(System.in);
         int n = scanner.nextInt();
-        Set<Segment> segments = new HashSet<Segment>();
+        Segment[] segments = new Segment[n];
         for (int i = 0; i < n; i++) {
             int start, end;
             start = scanner.nextInt();
             end = scanner.nextInt();
-            segments.add(new Segment(start, end));
+            segments[i] = new Segment(start, end);
         }
-        Segment[] s = segments.stream().toArray(Segment[]::new);
-        Arrays.sort(s);
-        Integer[] points = getOptimalPoints(s);
+        Set<Segment> s = new HashSet<Segment>(Arrays.asList(segments));
+        Segment[] newArray = s.stream().toArray(Segment[]::new);
+        Arrays.sort(newArray);
+        int[] points = getOptimalPoints(newArray);
         System.out.println(points.length);
         for (int point : points) {
             System.out.print(point + " ");
         }
 	}
-	public static Integer[] getOptimalPoints(Segment[] s) {
+	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++;
-			int temp = (int) points.get(points.size()-1);
-			while (index < s.length && s[index].start <= temp) {
-				if (s[index].end < temp)
+			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 = index + 1;
 			}
 		}
-		Integer[] results = new Integer[points.size()];
-		results = points.toArray(results);
-		return results;
+		return points.stream().mapToInt(i -> i).toArray();
 	}
 
 }
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java b/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
index 2f25158..5afbd5d 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
@@ -42,7 +42,155 @@ class CoveringSegmentsTest {
 		set.add(new CoveringSegments.Segment(3, 6));
 		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
 		Arrays.sort(s);
+		int[] results = CoveringSegments.getOptimalPoints(s);
+		assertEquals(3, results[0]);
+	}
+
+	@Test
+	void testGetOptimalPoints1() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(4, 7));
+		set.add(new CoveringSegments.Segment(1, 3));
+		set.add(new CoveringSegments.Segment(2, 5));
+		set.add(new CoveringSegments.Segment(5, 6));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(2, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints2() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 1));
+		set.add(new CoveringSegments.Segment(1, 1));
+		set.add(new CoveringSegments.Segment(1, 1));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
 		assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
 	}
 
+	@Test
+	void testGetOptimalPoints3() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 1));
+		set.add(new CoveringSegments.Segment(1, 2));
+		set.add(new CoveringSegments.Segment(1, 1));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints4() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(5, 6));
+		set.add(new CoveringSegments.Segment(3, 4));
+		set.add(new CoveringSegments.Segment(1, 2));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(3, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints5() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 1));
+		set.add(new CoveringSegments.Segment(2, 2));
+		set.add(new CoveringSegments.Segment(1, 1));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(2, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints6() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 5));
+		set.add(new CoveringSegments.Segment(2, 2));
+		set.add(new CoveringSegments.Segment(1, 1));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(2, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints7() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 5));
+		set.add(new CoveringSegments.Segment(2, 4));
+		set.add(new CoveringSegments.Segment(1, 3));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints8() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 4));
+		set.add(new CoveringSegments.Segment(2, 4));
+		set.add(new CoveringSegments.Segment(1, 3));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints9() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 7));
+		set.add(new CoveringSegments.Segment(1, 6));
+		set.add(new CoveringSegments.Segment(1, 3));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints10() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 7));
+		set.add(new CoveringSegments.Segment(1, 6));
+		set.add(new CoveringSegments.Segment(1, 3));
+		set.add(new CoveringSegments.Segment(7, 7));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(2, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints11() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 2));
+		set.add(new CoveringSegments.Segment(3, 4));
+		set.add(new CoveringSegments.Segment(6, 12));
+		set.add(new CoveringSegments.Segment(7, 8));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(3, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints12() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 15));
+		set.add(new CoveringSegments.Segment(2, 14));
+		set.add(new CoveringSegments.Segment(6, 12));
+		set.add(new CoveringSegments.Segment(7, 8));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(1, CoveringSegments.getOptimalPoints(s).length);
+	}
+
+	@Test
+	void testGetOptimalPoints13() {
+		Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+		set.add(new CoveringSegments.Segment(1, 15));
+		set.add(new CoveringSegments.Segment(2, 3));
+		set.add(new CoveringSegments.Segment(4, 8));
+		CoveringSegments.Segment[] s = set.stream().toArray(CoveringSegments.Segment[]::new);
+		Arrays.sort(s);
+		assertEquals(2, CoveringSegments.getOptimalPoints(s).length);
+	}
+
 }