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
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