blob: 4b83129ad56e9b436086ac8418820800097ccc5e (
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
public class NetworkPacket {
static class Request {
int arrivalTime;
int processTime;
Request(int arrivalTime, int processTime) {
this.arrivalTime = arrivalTime;
this.processTime = processTime;
}
}
static class Response {
boolean dropped;
int startTime;
Response(boolean dropped, int startTime) {
this.dropped = dropped;
this.startTime = startTime;
}
}
static class Buffer {
private int capacity;
private Deque<Integer> finishTime;
// My addition to the starter file
private int runningTimeCounter = 0;
// End of my addition to the starter file
Buffer(int capacity) {
this.capacity = capacity;
this.finishTime = new LinkedList<>();
}
Response processRequest(Request request) {
if (runningTimeCounter < request.arrivalTime)
if (finishTime.size() == 0)
runningTimeCounter = request.arrivalTime;
else if (finishTime.getLast() < request.arrivalTime)
runningTimeCounter = request.arrivalTime;
while (finishTime.size() > 0) {
int j = finishTime.getFirst();
if (j <= request.arrivalTime)
finishTime.pop();
else
break;
}
if (finishTime.size() >= capacity) {
return new Response(true, -1);
}
Response response = new Response(false, runningTimeCounter);
runningTimeCounter = runningTimeCounter + request.processTime;
if (finishTime.size() > 0)
finishTime.addLast(finishTime.getLast() + request.processTime);
else
finishTime.addLast(runningTimeCounter);
return response;
}
}
private static ArrayList<Request> ReadQueries(Scanner scanner) {
int requests_count = scanner.nextInt();
ArrayList<Request> requests = new ArrayList<>();
for (int i = 0; i < requests_count; ++i) {
int arrival_time = scanner.nextInt();
int process_time = scanner.nextInt();
requests.add(new Request(arrival_time, process_time));
}
return requests;
}
static ArrayList<Response> processRequests(ArrayList<Request> requests, Buffer buf) {
ArrayList<Response> responses = new ArrayList<>();
for (Request request : requests) {
responses.add(buf.processRequest(request));
}
return responses;
}
private static void PrintResponses(ArrayList<Response> responses) {
for (Response response : responses) {
if (response.dropped) {
System.out.println(-1);
} else {
System.out.println(response.startTime);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int bufferMaxSize = scanner.nextInt();
Buffer buffer = new Buffer(bufferMaxSize);
ArrayList<Request> requests = ReadQueries(scanner);
ArrayList<Response> responses = processRequests(requests, buffer);
PrintResponses(responses);
}
}
|
