summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java42
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java148
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);
+ }
+
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 17:47:23 +0000