From e314d433e66a6177c8a17e3fca5acc59005e1b06 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Tue, 29 Jan 2019 16:18:10 -0600 Subject: Network Packet done! It's not too bad, since I worked things out in Java first. 2 things are of note: 1. Java Deque's pop is Python Deque's popleft. 2. I didn't use an iterator to remove items. It seemed to work fine. --- sources/network_packet.py | 63 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 sources/network_packet.py (limited to 'sources/network_packet.py') diff --git a/sources/network_packet.py b/sources/network_packet.py new file mode 100644 index 0000000..46ac2fb --- /dev/null +++ b/sources/network_packet.py @@ -0,0 +1,63 @@ +# python3 + +from collections import namedtuple, deque + +Request = namedtuple("Request", ["arrived_at", "time_to_process"]) +Response = namedtuple("Response", ["was_dropped", "started_at"]) + + +class Buffer: + def __init__(self, capacity): + self.capacity = capacity + self.finish_time = deque() + self.running_time_counter = 0 + + def process(self, request): + if self.running_time_counter < request.arrived_at: + if len(self.finish_time) == 0: + self.running_time_counter = request.arrived_at + elif self.finish_time[-1] < request.arrived_at: + self.running_time_counter = request.arrived_at + + while len(self.finish_time) > 0: + j = self.finish_time[0] + if j <= request.arrived_at: + self.finish_time.popleft() + else: + break + + if len(self.finish_time) >= self.capacity: + return Response(True, -1) + + response = Response(False, self.running_time_counter) + self.running_time_counter = self.running_time_counter + request.time_to_process + if len(self.finish_time) > 0: + self.finish_time.append(self.finish_time[-1] + request.time_to_process) + else: + self.finish_time.append(self.running_time_counter) + return response + + +def process_requests(requests, buffer): + responses = [] + for request in requests: + responses.append(buffer.process(request)) + return responses + + +def main(): + buffer_size, n_requests = map(int, input().split()) + requests = [] + for _ in range(n_requests): + arrived_at, time_to_process = map(int, input().split()) + requests.append(Request(arrived_at, time_to_process)) + + buffer = Buffer(buffer_size) + responses = process_requests(requests, buffer) + + for response in responses: + print(response.started_at if not response.was_dropped else -1) + + +if __name__ == "__main__": + main() -- cgit v1.2.3