summaryrefslogtreecommitdiff
path: root/sources/network_packet.py
blob: 46ac2fb8ee38d753036d1a4c3c13699ca16b0767 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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()