diff options
| -rw-r--r-- | PlaygroundCpp/.settings/language.settings.xml | 4 | ||||
| -rw-r--r-- | 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 @@ <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 "${INPUTS}"" 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 "${INPUTS}"" 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 "${INPUTS}"" 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 "${INPUTS}"" 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] << " "; + } } |