summaryrefslogtreecommitdiff
path: root/Sources
diff options
context:
space:
mode:
authorHaidong Ji2019-03-05 14:49:08 -0600
committerHaidong Ji2019-03-05 14:49:08 -0600
commitfc4792aca6cb9a96e7ebce39e0416692bbe526ed (patch)
tree1a3c1cc213b4ef97594099347788110773ce1705 /Sources
parentcf6f4a6dcb62c21b5f498396d01e5323d42852a7 (diff)
Merging tables done!
Lots of fun getting this one. I modified the starter code significantly, so it's more like my Java code (I did deviate away with setID as int). I'm happy for 2 things: 1. Learned and practiced again of passing by reference and modifying vector<Table> elements through address 2. Debugging googletests with Eclipse, I tried it and it worked. I had to click forward a few steps before I can really see variables and their changes in the debugger. Very nice :)
Diffstat (limited to 'Sources')
-rw-r--r--Sources/DataStructure.cpp204
1 files changed, 111 insertions, 93 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 6085971..2c444df 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,117 +1,135 @@
-#include <iostream>
+#include <cstdio>
+#include <cstdlib>
#include <vector>
#include <algorithm>
-#include <queue>
+#include <iostream>
//#include <gtest/gtest.h>
-using std::vector;
using std::cin;
using std::cout;
-using std::pair;
-using std::make_pair;
-
-class JobQueue {
-private:
+using std::endl;
+using std::max;
+using std::vector;
- vector<int> assigned_workers_;
- vector<long long> start_times_;
+struct Table {
+ int numberOfRows;
+ int setID;
- void WriteResponse() const {
- for (size_t i = 0; i < jobs.size(); ++i) {
- cout << assigned_workers_[i] << " " << start_times_[i] << "\n";
- }
+ Table(int numberOfRows, int setID) :
+ numberOfRows(numberOfRows), setID(setID) {
}
+};
- void ReadData() {
- int m;
- cin >> num_workers >> m;
- jobs.resize(m);
- for (int i = 0; i < m; ++i)
- cin >> jobs[i];
- }
+int maximumNumberOfRows = -1;
+vector<int> parent;
+vector<int> rank;
+vector<Table> tables;
- void AssignJobs() {
- // Naive algorithm
- assigned_workers_.resize(jobs.size());
- start_times_.resize(jobs.size());
- vector<long long> next_free_time(num_workers, 0);
- for (size_t i = 0; i < jobs.size(); ++i) {
- int duration = jobs[i];
- int next_worker = 0;
- for (int j = 0; j < num_workers; ++j) {
- if (next_free_time[j] < next_free_time[next_worker])
- next_worker = j;
- }
- assigned_workers_[i] = next_worker;
- start_times_[i] = next_free_time[next_worker];
- next_free_time[next_worker] += duration;
- }
- }
+int find(int i) {
+ if (i != parent[i])
+ parent[i] = find(parent[i]);
+ return parent[i];
+}
-public:
- int num_workers;
- vector<int> jobs;
- void Solve() {
- ReadData();
- AssignJobsImproved();
- WriteResponse();
+void unite(int destination, int source) {
+ int destination_id = find(destination);
+ int source_id = find(source);
+ if (destination_id == source_id)
+ return;
+ if (rank[destination_id] > rank[source_id])
+ parent[source_id] = destination_id;
+ else {
+ parent[destination_id] = source_id;
+ if (rank[destination_id] == rank[source_id])
+ rank[source_id] = rank[source_id] + 1;
}
- const vector<int>& assigned_workers() const {
- return assigned_workers_;
- }
- const vector<long long>& start_times() const {
- return start_times_;
+}
+
+void merge(int destination, int source) {
+ int d = find(destination);
+ int s = find(source);
+ Table* realDestination = &tables[d];
+ Table* realSource = &tables[s];
+ if (d == s) {
+ return;
}
+ maximumNumberOfRows = max(maximumNumberOfRows,
+ tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows);
+ realDestination->numberOfRows = tables[realDestination->setID].numberOfRows
+ + tables[realSource->setID].numberOfRows;
+ realSource->numberOfRows = 0;
+ realSource->setID = d;
+ realDestination->setID = d;
+ unite(destination, source);
+}
- void AssignJobsImproved() {
- std::priority_queue<pair<long, int>> pq;
- assigned_workers_.resize(jobs.size());
- start_times_.resize(jobs.size());
+int main() {
+ int n, m;
+ cin >> n >> m;
- for (size_t i = 0; i < num_workers; ++i) {
- pq.push(make_pair(0, -i));
- }
+ parent.resize(n);
+ rank.resize(n);
+// tables.resize(n);
+ for (int i = 0; i < n; i++) {
+ int numberOfRows;
+ cin >> numberOfRows;
+ tables.push_back(Table(numberOfRows, i));
+// tables[i] = Table(numberOfRows, i);
+ parent[i] = i;
+ rank[i] = 0;
+ maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows);
+ }
+
+ for (int i = 0; i < m; i++) {
+ int destination, source;
+ cin >> destination >> source;
+ --destination;
+ --source;
- for (size_t i = 0; i < jobs.size(); ++i) {
- pair<long, int> l = pq.top();
- pq.pop();
- start_times_[i] = -l.first;
- assigned_workers_[i] = -l.second;
- pq.push(make_pair(l.first - jobs[i], l.second));
- }
+ merge(destination, source);
+ cout << maximumNumberOfRows << endl;
}
-};
-int main() {
- std::ios_base::sync_with_stdio(false);
- JobQueue job_queue;
- job_queue.Solve();
- return 0;
+ return 0;
}
-//TEST(ParralelProcessing, t) {
-// vector<int> jobs = { 1, 2, 3, 4, 5 };
-// vector<int> expected_assigned_workers = { 0, 1, 0, 1, 0 };
-// vector<long long> expected_start_times = { 0, 0, 1, 2, 4 };
-// JobQueue jq;
-// jq.num_workers = 2;
-// jq.jobs = jobs;
-// jq.AssignJobsImproved();
-// ASSERT_EQ(expected_assigned_workers, jq.assigned_workers());
-// ASSERT_EQ(expected_start_times, jq.start_times());
+//TEST(MergingTables, t) {
+// maximumNumberOfRows = 1;
+// rank = {0, 0, 0, 0, 0};
+// parent = {0, 1, 2, 3, 4};
+// tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)};
+//
+// merge(2, 4);
+// ASSERT_EQ(2, maximumNumberOfRows);
+//
+// merge(1, 3);
+// ASSERT_EQ(2, maximumNumberOfRows);
+//
+// merge(0, 3);
+// ASSERT_EQ(3, maximumNumberOfRows);
+//
+// merge(4, 3);
+// ASSERT_EQ(5, maximumNumberOfRows);
+//
+// merge(4, 2);
+// ASSERT_EQ(5, maximumNumberOfRows);
//}
//
-//TEST(ParralelProcessing, t1) {
-// vector<int> jobs = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
-// 1, 1 };
-// vector<int> expected_assigned_workers = { 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2,
-// 3, 0, 1, 2, 3, 0, 1, 2, 3 };
-// vector<long long> expected_start_times = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2,
-// 2, 3, 3, 3, 3, 4, 4, 4, 4 };
-// JobQueue jq;
-// jq.num_workers = 4;
-// jq.jobs = jobs;
-// jq.AssignJobsImproved();
-// ASSERT_EQ(expected_assigned_workers, jq.assigned_workers());
-// ASSERT_EQ(expected_start_times, jq.start_times());
+//TEST(MergingTables, t1) {
+// maximumNumberOfRows = 10;
+// rank = {0, 0, 0, 0, 0, 0};
+// parent = {0, 1, 2, 3, 4, 5};
+// tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)};
+//
+// merge(5, 5);
+// ASSERT_EQ(10, maximumNumberOfRows);
+//
+// merge(5, 4);
+// ASSERT_EQ(10, maximumNumberOfRows);
+//
+// merge(4, 3);
+// ASSERT_EQ(10, maximumNumberOfRows);
+//
+// merge(3, 2);
+// ASSERT_EQ(11, maximumNumberOfRows);
//}