summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-09-27 20:23:57 -0500
committerHaidong Ji2018-09-27 20:23:57 -0500
commitf58eef05b96e69194da4cb14af083d4c99d617d4 (patch)
tree7c99b55bca556e78e2966b51ce8aedd55d17d13a
parent81a53382da84d0bb85d2530c02644e6937075586 (diff)
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!
-rw-r--r--PlaygroundCpp/.settings/language.settings.xml4
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp115
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 @@
<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
- <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939399062786427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+ <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939321890483387581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
<language-scope id="org.eclipse.cdt.core.gcc"/>
@@ -33,7 +33,7 @@
<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
- <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939399062786427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+ <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939321890483387581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
<language-scope id="org.eclipse.cdt.core.gcc"/>
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 <algorithm>
#include <iostream>
+#include <climits>
#include <vector>
-#include <algorithm>
//#include <gtest/gtest.h>
using std::vector;
-static long getMaxDotProduct(vector<int> a, vector<int> 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<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 result;
+ return points;
}
-//TEST(MaxDotProduct, Max1) {
-// vector<int> a = { 60, 100, 120 };
-// vector<int> 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<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(MaxDotProduct, Max2) {
-// vector<int> a = { 23 };
-// vector<int> 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<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(MaxDotProduct, Max3) {
-// vector<int> a = { 1,3,-5 };
-// vector<int> 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<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() {
- size_t n;
- std::cin >> n;
- vector<int> 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<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] << " ";
+ }
}