summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java95
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java188
2 files changed, 279 insertions, 4 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
index 0134ebb..8cad411 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/CoveringSegments.java
@@ -1,9 +1,100 @@
+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 void main(String[] args) {
- // TODO Auto-generated method stub
+ public static class Segment implements Comparable<Segment> {
+ 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<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();
+ Segment[] segments = new Segment[n];
+ for (int i = 0; i < n; i++) {
+ int start, end;
+ start = scanner.nextInt();
+ end = scanner.nextInt();
+ segments[i] = new Segment(start, end);
+ }
+ 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 int[] getOptimalPoints(Segment[] s) {
+ int index = 0;
+ List<Integer> points = new ArrayList<Integer>();
+ while (index < s.length) {
+ points.add(s[index].end);
+ 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 + 1;
+ }
+ }
+ return points.stream().mapToInt(i -> i).toArray();
+ }
}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java b/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
index 8f2d191..5afbd5d 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/CoveringSegmentsTest.java
@@ -1,12 +1,196 @@
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 test() {
- CoveringSegments.Segment s1 = new CoveringSegments.Segment(1,3);
+ 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<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>(Arrays.asList(s));
+ assertEquals(2, set.size());
+ }
+
+ @Test
+ void testGetOptimalPoints() {
+ Set<CoveringSegments.Segment> set = new HashSet<CoveringSegments.Segment>();
+ 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);
+ 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-23 12:41:33 +0000