From 6cae1e170d6f586a18577f74b26254f9cf325adf Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Fri, 20 Jan 2023 18:53:13 +0100
Subject: add

---
 Year_2/Algorithms/activity.cc | 95 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 95 insertions(+)
 create mode 100644 Year_2/Algorithms/activity.cc

(limited to 'Year_2')

diff --git a/Year_2/Algorithms/activity.cc b/Year_2/Algorithms/activity.cc
new file mode 100644
index 0000000..5009780
--- /dev/null
+++ b/Year_2/Algorithms/activity.cc
@@ -0,0 +1,95 @@
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef pair<int, int> pi;
+
+int
+find(int j, int* w, int* o, int* p)
+{
+    int c { 0 };
+    while (j > 0) {
+        if (w[j] + o[p[j]] > o[j - 1]) {
+            c += w[j];
+            j = p[j];
+        } else {
+            j--;
+        }
+    }
+
+    return c;
+}
+
+int
+activity(vector<pi> A)
+{
+    int n = A.size() + 1;
+    int* p = new int[n];
+    int* w = new int[n];
+    int* o = new int[n];
+    int i, j;
+
+    o[0] = w[0] = p[0] = 0;
+
+    for (i = 1; i < n; ++i) {
+        p[i] = 0;
+        w[i] = A[i - 1].second - A[i - 1].first;
+    }
+
+    for (i = n - 1; i > 0; --i) {
+        for (j = 1; j < n; ++j)
+            if (A[j - 1].second <= A[i - 1].first)
+                p[i]++;
+    }
+
+    for (i = 1; i < n; ++i) {
+        o[i] = max(w[i] + o[p[i]], o[i - 1]);
+    }
+
+    int res = find(n - 1, w, o, p);
+
+    delete[] p;
+    delete[] w;
+    delete[] o;
+
+    return res;
+}
+
+int
+main(int argc, char** argv)
+{
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+
+    int ts = (argc > 1) ? stoi(argv[1]) : 100;
+    int n;
+
+    for (int i = 0; i < ts; ++i) {
+        fin >> n;
+        string ch;
+        int s;
+        int e;
+        vector<pi> a;
+
+        for (int j = 0; j < n; ++j) {
+            fin >> ch;
+            s = stoi(ch.substr(1, ch.length()));
+            fin >> ch;
+            e = stoi(ch.substr(0, ch.length() - 1));
+            a.push_back({ s, e });
+        }
+
+        sort(a.begin(), a.end(), [](pi const& x, pi const& y) {
+            return x.second < y.second;
+        });
+
+        fout << activity(a) << endl;
+    }
+
+    fin.close();
+    fout.close();
+    return 0;
+}
-- 
cgit v1.2.3-18-g5258