#include #include #include #include //#include using std::vector; struct Segment { int start, end; bool operator==(const Segment &s1) { return (start == s1.start && end == s1.end); } }; vector optimal_points(vector &segments) { int index = 0; vector 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 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 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 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 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 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 points = optimal_points(segments); std::cout << points.size() << "\n"; for (size_t i = 0; i < points.size(); ++i) { std::cout << points[i] << " "; } }