diff options
| -rw-r--r-- | Sources/DataStructure.cpp | 188 |
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; } + |