Parallel processing job queue done!

I used C++'s priority_queue (queue.h) and C++'s own pair data structure.
Unlike Python and Java's similar data structure, C++'s priority_queue
pops in reverse order, so I had to negate the value, and negate back
when adding them to vectors. Cool use of pair. Fun stuff :)

1 files changed, 82 insertions, 83 deletions

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index f3d46be..6085971 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,118 +1,117 @@
 #include <iostream>
 #include <vector>
 #include <algorithm>
+#include <queue>
 //#include <gtest/gtest.h>
 
 using std::vector;
 using std::cin;
 using std::cout;
-using std::swap;
 using std::pair;
 using std::make_pair;
 
-class HeapBuilder {
+class JobQueue {
 private:
-	vector<int> data_;
-//	vector<pair<int, int> > swaps_;
 
-//	void GenerateSwaps() {
-//		swaps_.clear();
-//		// The following naive implementation just sorts
-//		// the given sequence using selection sort algorithm
-//		// and saves the resulting sequence of swaps.
-//		// This turns the given array into a heap,
-//		// but in the worst case gives a quadratic number of swaps.
-//		//
-//		for (size_t i = 0; i < data_.size(); ++i)
-//			for (size_t j = i + 1; j < data_.size(); ++j) {
-//				if (data_[i] > data_[j]) {
-//					swap(data_[i], data_[j]);
-//					swaps_.push_back(make_pair(i, j));
-//				}
-//			}
-//	}
+	vector<int> assigned_workers_;
+	vector<long long> start_times_;
 
-public:
-	vector<pair<int, int>> swaps;
 	void WriteResponse() const {
-		cout << swaps.size() << "\n";
-		for (size_t i = 0; i < swaps.size(); ++i) {
-			cout << swaps[i].first << " " << swaps[i].second << "\n";
+		for (size_t i = 0; i < jobs.size(); ++i) {
+			cout << assigned_workers_[i] << " " << start_times_[i] << "\n";
 		}
 	}
 
 	void ReadData() {
-		int n;
-		cin >> n;
-		data_.resize(n);
-		for (int i = 0; i < n; ++i)
-			cin >> data_[i];
+		int m;
+		cin >> num_workers >> m;
+		jobs.resize(m);
+		for (int i = 0; i < m; ++i)
+			cin >> jobs[i];
 	}
 
-	// Please note the for loop below. Initially I copied the for loop from my
-	// Java code, but it doesn't work in C++. Changing it to while loop worked!
-	// It was better with the while loop anyway, much clearer to me.
-	void UpdateSwaps(vector<int> &data) {
-		int j = (data.size() - 1) / 2;
-		while (j >= 0) {
-			siftDown(j, data);
-			j = j - 1;
-		}
-//		for (size_t i = j; i >= 0; i--) {
-//			siftDown(i, data);
-//		}
-	}
-	void siftDown(int i, vector<int> &data) {
-		int maxIndex = i;
-		size_t l = 2 * i + 1;
-		if (l < data.size() && data[l] < data[maxIndex])
-			maxIndex = l;
-		size_t r = 2 * i + 2;
-		if (r < data.size() && data[r] < data[maxIndex])
-			maxIndex = r;
-		if (i != maxIndex) {
-			swap(data[i], data[maxIndex]);
-			swaps.push_back(make_pair(i, maxIndex));
-			siftDown(maxIndex, data);
+	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;
 		}
 	}
+
+public:
+	int num_workers;
+	vector<int> jobs;
 	void Solve() {
 		ReadData();
-//		GenerateSwaps();
-		UpdateSwaps(data_);
+		AssignJobsImproved();
 		WriteResponse();
 	}
+	const vector<int>& assigned_workers() const {
+		return assigned_workers_;
+	}
+	const vector<long long>& start_times() const {
+		return start_times_;
+	}
+
+	void AssignJobsImproved() {
+		std::priority_queue<pair<long, int>> pq;
+		assigned_workers_.resize(jobs.size());
+		start_times_.resize(jobs.size());
+
+		for (size_t i = 0; i < num_workers; ++i) {
+			pq.push(make_pair(0, -i));
+		}
+
+		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));
+		}
+	}
 };
 
 int main() {
-//	vector<int> data = { 5, 4, 3, 2, 1 };
-//	HeapBuilder heap_builder;
-//	heap_builder.UpdateSwaps(data);
-//	heap_builder.WriteResponse();
-
-	std::ios_base::sync_with_stdio(false);
-	HeapBuilder heap_builder;
-	heap_builder.Solve();
-	return 0;
+  std::ios_base::sync_with_stdio(false);
+  JobQueue job_queue;
+  job_queue.Solve();
+  return 0;
 }
 
-//TEST(BuildHeap, t) {
-//	vector<int> data = {5, 4, 3, 2, 1};
-//	HeapBuilder heap_builder;
-//	heap_builder.UpdateSwaps(data);
-//    ASSERT_EQ(3, heap_builder.swaps.size());
-//    ASSERT_EQ(1, heap_builder.swaps[0].first);
-//    ASSERT_EQ(4, heap_builder.swaps[0].second);
-//    ASSERT_EQ(0, heap_builder.swaps[1].first);
-//    ASSERT_EQ(1, heap_builder.swaps[1].second);
-//    ASSERT_EQ(1, heap_builder.swaps[2].first);
-//    ASSERT_EQ(3, heap_builder.swaps[2].second);
+//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(BuildHeap, t1) {
-//	vector<int> data = {1, 2, 3, 4, 5};
-//	HeapBuilder heap_builder;
-//	heap_builder.UpdateSwaps(data);
-//    ASSERT_EQ(0, heap_builder.swaps.size());
+//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());
 //}
-//