summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Sources/DataStructure.cpp188
1 files changed, 114 insertions, 74 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 91fdf86..e76d5be 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,101 +1,141 @@
#include <iostream>
#include <queue>
-#include <algorithm>
#include <vector>
//#include <gtest/gtest.h>
-using std::vector;
-using std::queue;
-
-class Node;
+struct Request {
+ Request(int arrival_time, int process_time) :
+ arrival_time(arrival_time), process_time(process_time) {
+ }
-class Node {
-public:
- int key;
- Node *parent;
- vector<Node *> children;
+ int arrival_time;
+ int process_time;
+};
- Node() {
- this->parent = NULL;
+struct Response {
+ Response(bool dropped, int start_time) :
+ dropped(dropped), start_time(start_time) {
}
- void setParent(Node *theParent) {
- parent = theParent;
- parent->children.push_back(this);
- }
+ bool dropped;
+ int start_time;
};
-int treeLevelCounter(vector<Node> &nodes, int rootIndex) {
- int levelCounter = 1;
- queue<Node *> q;
- int popCount = 0;
- int childrenCount = nodes[rootIndex].children.size();
- int grandChildrenCount = 0;
- for (int i = 0; i < childrenCount; i++) {
- q.push(nodes[rootIndex].children[i]);
+class Buffer {
+public:
+ Buffer(int capacity) :
+ capacity_(capacity), finish_time_() {
}
- while (!q.empty()) {
- if (popCount < childrenCount) {
- Node *n = q.front();
- q.pop();
- int i = n->children.size();
- if (i != 0) {
- for (int j = 0; j < i; j++) {
- q.push(n->children[j]);
- }
- }
- grandChildrenCount = grandChildrenCount + i;
- popCount = popCount + 1;
- } else {
- popCount = 0;
- childrenCount = grandChildrenCount;
- grandChildrenCount = 0;
- levelCounter = levelCounter + 1;
+
+ Response Process(const Request &request) {
+ // write your code here
+ if (runningTimeCounter_ < request.arrival_time) {
+ if (finish_time_.size() == 0)
+ runningTimeCounter_ = request.arrival_time;
+ else if (finish_time_.back() < request.arrival_time)
+ runningTimeCounter_ = request.arrival_time;
}
- }
- return levelCounter + 1;
-}
-int getHeight(vector<int> &a) {
- vector<Node> nodes;
- nodes.resize(a.size());
- int rootIndex = 0;
- for (size_t i = 0; i < a.size(); i++) {
- int parentIndex = a[i];
- if (parentIndex == -1) {
- rootIndex = i;
- } else {
- nodes[i].setParent(&nodes[parentIndex]);
+ while (finish_time_.size() > 0) {
+ int j = finish_time_.front();
+ if (j <= request.arrival_time)
+ finish_time_.pop();
+ else
+ break;
}
+
+ if (finish_time_.size() >= capacity_) {
+ return Response(true, -1);
+ }
+ Response response = Response(false, runningTimeCounter_);
+ runningTimeCounter_ = runningTimeCounter_ + request.process_time;
+ if (finish_time_.size() > 0)
+ finish_time_.push(finish_time_.back() + request.process_time);
+ else
+ finish_time_.push(runningTimeCounter_);
+ return response;
+
}
- return treeLevelCounter(nodes, rootIndex);
+private:
+ size_t capacity_;
+ std::queue<int> finish_time_;
+ int runningTimeCounter_ = 0;
+};
+
+std::vector<Request> ReadRequests() {
+ std::vector<Request> requests;
+ int count;
+ std::cin >> count;
+ for (int i = 0; i < count; ++i) {
+ int arrival_time, process_time;
+ std::cin >> arrival_time >> process_time;
+ requests.push_back(Request(arrival_time, process_time));
+ }
+ return requests;
}
-//TEST(GetTreeHeight, t1) {
-// vector<int> a = {4, -1, 4, 1, 1};
-// ASSERT_EQ(3, getHeight(a));
+std::vector<Response> ProcessRequests(const std::vector<Request> &requests,
+ Buffer *buffer) {
+ std::vector<Response> responses;
+ for (size_t i = 0; i < requests.size(); ++i)
+ responses.push_back(buffer->Process(requests[i]));
+ return responses;
+}
+
+void PrintResponses(const std::vector<Response> &responses) {
+ for (size_t i = 0; i < responses.size(); ++i)
+ std::cout << (responses[i].dropped ? -1 : responses[i].start_time)
+ << std::endl;
+}
+
+//TEST(ProcessRequests, t) {
+// int bufferMaxSize = 1;
+// Buffer buf = Buffer(bufferMaxSize);
+// std::vector<Request> requests;
+// std::vector<Response> responses = ProcessRequests(requests, &buf);
+// ASSERT_EQ(0, responses.size());
//}
//
-//TEST(GetTreeHeight, t2) {
-// vector<int> a = {-1, 0, 4, 0, 3};
-// ASSERT_EQ(4, getHeight(a));
+//TEST(ProcessRequests, t1) {
+// int bufferMaxSize = 1;
+// Buffer buf = Buffer(bufferMaxSize);
+// std::vector<Request> requests = {Request(0, 1)};
+// std::vector<Response> responses = ProcessRequests(requests, &buf);
+// ASSERT_EQ(1, responses.size());
+// ASSERT_EQ(false, responses[0].dropped);
//}
//
-//TEST(GetTreeHeight, t3) {
-// vector<int> a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1};
-// ASSERT_EQ(4, getHeight(a));
+//TEST(ProcessRequests, t2) {
+// int bufferMaxSize = 1;
+// Buffer buf = Buffer(bufferMaxSize);
+// std::vector<Request> requests = {Request(0, 1), Request(0, 1)};
+// std::vector<Response> responses = ProcessRequests(requests, &buf);
+// ASSERT_EQ(2, responses.size());
+// ASSERT_EQ(false, responses[0].dropped);
+// ASSERT_EQ(0, responses[0].start_time);
+// ASSERT_EQ(true, responses[1].dropped);
//}
//
-//TEST(GetTreeHeight, t4) {
-// vector<int> a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5};
-// ASSERT_EQ(6, getHeight(a));
+//TEST(ProcessRequests, t3) {
+// int bufferMaxSize = 1;
+// Buffer buf = Buffer(bufferMaxSize);
+// std::vector<Request> requests = {Request(0, 1), Request(1, 1)};
+// std::vector<Response> responses = ProcessRequests(requests, &buf);
+// ASSERT_EQ(2, responses.size());
+// ASSERT_EQ(false, responses[0].dropped);
+// ASSERT_EQ(0, responses[0].start_time);
+// ASSERT_EQ(false, responses[1].dropped);
+// ASSERT_EQ(1, responses[1].start_time);
//}
int main() {
- size_t an;
- std::cin >> an;
- vector<int> a(an);
- for (size_t i = 0; i < an; i++) {
- std::cin >> a[i];
- }
- std::cout << getHeight(a) << std::endl;
+ int size;
+ std::cin >> size;
+ std::vector<Request> requests = ReadRequests();
+
+ Buffer buffer(size);
+ std::vector<Response> responses = ProcessRequests(requests, &buffer);
+
+ PrintResponses(responses);
+ return 0;
}
+