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/Sources/Playground.cpp | 115 ++++++++++++++++++++++++++---------
 1 file changed, 85 insertions(+), 30 deletions(-)

(limited to 'PlaygroundCpp/Sources')

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] << " ";
+	}
 }
-- 
cgit v1.2.3