From f58eef05b96e69194da4cb14af083d4c99d617d4 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 27 Sep 2018 20:23:57 -0500
Subject: Covering segments/Collecting Signature done!
Really fun to implement it in C++. Learned std::sort, std::unique, ==
overloading for struct for std::unique to work. Good stuff!---
PlaygroundCpp/.settings/language.settings.xml | 4 +-
PlaygroundCpp/Sources/Playground.cpp | 115 +++++++++++++++++++-------
2 files changed, 87 insertions(+), 32 deletions(-)
diff --git a/PlaygroundCpp/.settings/language.settings.xml b/PlaygroundCpp/.settings/language.settings.xml
index bbdba31..f5ddb15 100644
--- a/PlaygroundCpp/.settings/language.settings.xml
+++ b/PlaygroundCpp/.settings/language.settings.xml
@@ -11,7 +11,7 @@
-
+
@@ -33,7 +33,7 @@
-
+
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index e79d68e..26e02f2 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,47 +1,102 @@
+#include
#include
+#include
#include
-#include
//#include
using std::vector;
-static long getMaxDotProduct(vector a, vector b) {
- std::sort(a.begin(), a.end());
- std::sort(b.begin(), b.end());
- long result = 0;
- for (int i = 0; i < b.size(); i++) {
- result = (long) a[i]*b[i]+result;
+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 result;
+ return points;
}
-//TEST(MaxDotProduct, Max1) {
-// vector a = { 60, 100, 120 };
-// vector b = { 20, 50, 30 };
-// ASSERT_EQ(getMaxDotProduct(a, b), 10200);
+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(MaxDotProduct, Max2) {
-// vector a = { 23 };
-// vector b = { 39 };
-// ASSERT_EQ(getMaxDotProduct(a, b), 897);
+//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(MaxDotProduct, Max3) {
-// vector a = { 1,3,-5 };
-// vector b = { -2,4,1 };
-// ASSERT_EQ(getMaxDotProduct(a, b), 23);
+//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() {
- size_t n;
- std::cin >> n;
- vector a(n), b(n);
- for (size_t i = 0; i < n; i++) {
- std::cin >> a[i];
- }
- for (size_t i = 0; i < n; i++) {
- std::cin >> b[i];
- }
- std::cout << getMaxDotProduct(a, b) << std::endl;
+ 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] << " ";
+ }
}
--
cgit v1.2.3