summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp128
1 files changed, 82 insertions, 46 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index aff2024..dbb916c 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,61 +1,97 @@
-#include <vector>
+#include <algorithm>
#include <iostream>
+#include <climits>
+#include <vector>
//#include <gtest/gtest.h>
using std::vector;
-long mergeInversionCount(vector<int> &B, vector<int> &C, vector<int> &D) {
- long count = 0;
- while (B.size() != 0 && C.size() != 0) {
- int b = B[0];
- int c = C[0];
- if (b <= c) {
- D.push_back(b);
- B.erase(B.begin());
- } else {
- count += B.size();
- D.push_back(c);
- C.erase(C.begin());
- }
+struct Segment {
+ int start, end;
+ bool operator==(const Segment &s1) {
+ return (start == s1.start && end == s1.end);
}
- D.insert(D.end(), B.begin(), B.end());
- D.insert(D.end(), C.begin(), C.end());
- return count;
+};
+
+bool sortSeg(Segment i, Segment j) {
+ if (i.start == j.start) {
+ return i.end < j.end;
+ }
+ return i.start < j.start;
}
-long getInversionCountFromList(vector<int> &A, vector<int> &D) {
- long numberOfInversions = 0;
- if (A.size() == 1) {
- D.push_back(A[0]);
- return 0;
+vector<int> fast_count_segments(vector<int> starts, vector<int> ends,
+ vector<int> points) {
+ // Implement algo described here, really clever:
+ // https://www.coursera.org/learn/algorithmic-toolbox/discussions/all/threads/QJ1jK9wNEeWdPBL2iFTrAw/replies/Ihiw4txhEeWK5g7mfcS2Xw/comments/oyAMaeIiEeWyqwpvChh66Q
+ // l->1, p->2, r->3 for Segment.end property
+ vector<Segment> s(starts.size() + ends.size() + points.size());
+ vector<Segment> p(points.size());
+ Segment tempSeg;
+ for (int i = 0; i < p.size(); i++) {
+ tempSeg = {points[i], i};
+ p[i] = tempSeg;
+ tempSeg = {points[i], 2};
+ s[2 * starts.size() + i] = tempSeg;
+ }
+ for (int i = 0; i < starts.size(); i++) {
+ tempSeg = {starts[i], 1};
+ s[i] = tempSeg;
+ tempSeg = {ends[i], 3};
+ s[i + starts.size()] = tempSeg;
+ }
+ std::sort(s.begin(), s.end(), sortSeg);
+ std::sort(p.begin(), p.end(), sortSeg);
+ vector<int> results(points.size());
+ int count = 0;
+ int j = 0;
+ for (int i = 0; i < s.size(); i++) {
+ if (s[i].end == 1) {
+ count = count + 1;
+ }
+ if (s[i].end == 2) {
+ results[j] = count;
+ j = j + 1;
+ }
+ if (s[i].end == 3) {
+ count = count - 1;
+ }
+ }
+ vector<int> finalResults(points.size());
+ for (int i = 0; i < finalResults.size(); i++) {
+ finalResults[p[i].end] = results[i];
}
- int m = A.size() / 2;
- vector<int> D1;
- vector<int>::const_iterator first = A.begin();
- vector<int>::const_iterator last = A.begin() + m;
- vector<int> newVec(first, last);
- numberOfInversions += getInversionCountFromList(newVec, D1);
- vector<int> D2;
- vector<int>::const_iterator ffirst = A.begin() + m;
- vector<int>::const_iterator llast = A.end();
- vector<int> newVecc(ffirst, llast);
- numberOfInversions += getInversionCountFromList(newVecc, D2);
- long mergeCount = mergeInversionCount(D1, D2, D);
- return numberOfInversions + mergeCount;
+ return finalResults;
}
-//TEST(InversionCount, test1) {
-// vector<int> a = { 2, 3, 9, 2, 2 };
-// vector<int> result(5);
-// ASSERT_EQ(4, getInversionCountFromList(a, result));
+//TEST(SortSegment, Sort1) {
+// vector<int> starts = { 0, 7 };
+// vector<int> ends = { 5, 10 };
+// vector<int> points = { 1, 6, 11 };
+// vector<int> results = { 1, 0, 0 };
+//
+// vector<int> cnt = fast_count_segments(starts, ends, points);
+//
+// ASSERT_EQ(cnt[0], 1);
+// ASSERT_EQ(cnt[1], 0);
+// ASSERT_EQ(cnt[2], 0);
+// ASSERT_EQ(cnt.size(), 3);
//}
int main() {
- int n;
- std::cin >> n;
- vector<int> a(n);
- for (size_t i = 0; i < a.size(); i++) {
- std::cin >> a[i];
+ int n, m;
+ std::cin >> n >> m;
+ vector<int> starts(n), ends(n);
+ for (size_t i = 0; i < starts.size(); i++) {
+ std::cin >> starts[i] >> ends[i];
+ }
+ vector<int> points(m);
+ for (size_t i = 0; i < points.size(); i++) {
+ std::cin >> points[i];
+ }
+ //use fast_count_segments
+ vector<int> cnt = fast_count_segments(starts, ends, points);
+ for (size_t i = 0; i < cnt.size(); i++) {
+ std::cout << cnt[i] << ' ';
}
- vector<int> b(a.size());
- std::cout << getInversionCountFromList(a, b) << '\n';
}
+