From 9d38fc09a4cd5a1b187b77b8f62768a2e59752de Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Wed, 26 Sep 2018 20:55:07 -0500 Subject: 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.--- .../sources/CoveringSegments.java | 42 ++++-- .../tests/CoveringSegmentsTest.java | 148 +++++++++++++++++++++ 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 segments = new HashSet(); +// 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 segments = new HashSet(); + 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 s = new HashSet(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 points = new ArrayList(); 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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 set = new HashSet(); + 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); + } + } -- cgit v1.2.3