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 { + 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 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); + 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 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) + 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 set = new HashSet(Arrays.asList(s)); + assertEquals(2, set.size()); + } + + @Test + void testGetOptimalPoints() { + Set set = new HashSet(); + 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