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
101
102
|
#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
//#include <gtest/gtest.h>
using std::vector;
struct Segment {
int start, end;
bool operator==(const Segment &s1) {
return (start == s1.start && end == s1.end);
}
};
vector<int> optimal_points(vector<Segment> &segments) {
int index = 0;
vector<int> points;
while (index < segments.size()) {
points.push_back(segments[index].end);
index = index + 1;
while (index < segments.size()
&& segments[index].start <= points[points.size() - 1]) {
if (segments[index].end < points[points.size() - 1]) {
points.back() = segments[index].end;
}
index = index + 1;
}
}
return points;
}
bool sortSeg(Segment i, Segment j) {
if (i.start == j.start) {
return i.end < j.end;
}
return i.start < j.start;
}
//TEST(SortSegment, Sort1) {
// Segment OneFive, TwoFour;
// OneFive.start = 1;
// OneFive.end = 5;
// TwoFour.start = 2;
// TwoFour.end = 4;
// vector<Segment> a = { TwoFour, OneFive };
// std::sort(a.begin(), a.end(), sortSeg);
// ASSERT_EQ(a.at(0).start, 1);
//}
//
//TEST(SortSegment, Sort2) {
// Segment OneFive, OneFour;
// OneFive.start = 1;
// OneFive.end = 5;
// OneFour.start = 1;
// OneFour.end = 4;
// vector<Segment> a = { OneFive, OneFour };
// std::sort(a.begin(), a.end(), sortSeg);
// ASSERT_EQ(a.at(0).end, 4);
//}
//
//TEST(SortSegment, SortWithDups1) {
// Segment OneFive, OneFour;
// OneFive.start = 1;
// OneFive.end = 5;
// OneFour.start = 1;
// OneFour.end = 4;
// vector<Segment> a = { OneFive, OneFour, OneFive};
// std::sort(a.begin(), a.end(), sortSeg);
// ASSERT_EQ(a.at(0).end, 4);
// ASSERT_EQ(a.size(), 3);
//}
//
//TEST(SortSegment, SortAndRemoveDups1) {
// Segment OneFive, OneFour;
// OneFive.start = 1;
// OneFive.end = 5;
// OneFour.start = 1;
// OneFour.end = 4;
// vector<Segment> a = { OneFive, OneFour, OneFive};
// std::sort(a.begin(), a.end(), sortSeg);
// auto last = std::unique(a.begin(), a.end());
// a.erase(last, a.end());
// ASSERT_EQ(a.size(), 2);
//}
int main() {
int n;
std::cin >> n;
vector<Segment> segments(n);
for (size_t i = 0; i < segments.size(); ++i) {
std::cin >> segments[i].start >> segments[i].end;
}
std::sort(segments.begin(), segments.end(), sortSeg);
auto last = std::unique(segments.begin(), segments.end());
segments.erase(last, segments.end());
vector<int> points = optimal_points(segments);
std::cout << points.size() << "\n";
for (size_t i = 0; i < points.size(); ++i) {
std::cout << points[i] << " ";
}
}
|
