blob: 8cad4113edfe58daae0ce5b19ef87c51022dbd40 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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 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();
}
}
|
