diff options
author | Haidong Ji | 2018-09-26 20:55:07 -0500 |
---|---|---|
committer | Haidong Ji | 2018-09-26 20:55:07 -0500 |
commit | 9d38fc09a4cd5a1b187b77b8f62768a2e59752de (patch) | |
tree | efadb6d19d40a4586c4e268fb642b6d1a08cd372 /AlgoDesignAndTechniqueEdxJava | |
parent | 68cad41492dc546c7f9a5459c991892d5b01abca (diff) |
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.
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java | 42 | ||||
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/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<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); + } + } |