Problem Description You are given a series of incoming network packets, and your task is to simulate their processing. Packets arrive in some order. For each packet number 𝑖, you know the time when it arrived 𝐴𝑖 and the time it takes the processor to process it 𝑃𝑖 (both in milliseconds). There is only one processor, and it processes the incoming packets in the order of their arrival. If the processor started to process some packet, it doesn’t interrupt or stop until it finishes the processing of this packet, and the processing of packet 𝑖 takes exactly 𝑃𝑖 milliseconds. The computer processing the packets has a network buffer of fixed size 𝑆. When packets arrive, they are stored in the buffer before being processed. However, if the buffer is full when a packet arrives (there are 𝑆 packets which have arrived before this packet, and the computer hasn’t finished processing any of them), it is dropped and won’t be processed at all. If several packets arrive at the same time, they are first all stored in the buffer (some of them may be dropped because of that — those which are described later in the input). The computer processes the packets in the order of their arrival, and it starts processing the next available packet from the buffer as soon as it finishes processing the previous one. If at some point the computer is not busy, and there are no packets in the buffer, the computer just waits for the next packet to arrive. Note that a packet leaves the buffer and frees the space in the buffer as soon as the computer finishes processing it.

Input Format The first line of the input contains the size 𝑆 of the buffer and the number 𝑛 of incoming network packets. Each of the next 𝑛 lines contains two numbers. 𝑖-th line contains the time of arrival 𝐴𝑖 and the processing time 𝑃𝑖 (both in milliseconds) of the 𝑖-th packet. It is guaranteed that the sequence of arrival times is non-decreasing (however, it can contain the exact same times of arrival in milliseconds — in this case the packet which is earlier in the input is considered to have arrived earlier).

Constraints All the numbers in the input are integers. 1 ≤ 𝑆 ≤ 105; 0 ≤ 𝑛 ≤ 105; 0 ≤ 𝐴𝑖 ≤ 106; 0≤𝑃𝑖 ≤103;𝐴𝑖 ≤𝐴𝑖+1 for1≤𝑖≤𝑛−1.

Output Format For each packet output either the moment of time (in milliseconds) when the processor began processing it or −1 if the packet was dropped (output the answers for the packets in the same order as the packets are given in the input).

Sample 1. Input:

10

Output:

Explanation: If there are no packets, you shouldn’t output anything.

Sample 2. Input:

1 1
0 0

Output:

0

Explanation: The only packet arrived at time 0, and computer started processing it immediately.

Sample 3. Input:

 1 2 
 0 1
 0 1

Output:

0
-1

Explanation: The first packet arrived at time 0, the second packet also arrived at time 0, but was dropped, because the network buffer has size 1 and it was full with the first packet already. The first packet started processing at time 0, and the second packet was not processed at all.

Sample 4. Input:

 1 2
 0 1
 1 1

Output:

 0
 1

Explanation: The first packet arrived at time 0, the computer started processing it immediately and finished at time 1. The second packet arrived at time 1, and the computer started processing it immediately.

My Solution

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

class Request {
    public Request(int arrival_time, int process_time) {
        this.arrival_time = arrival_time;
        this.process_time = process_time;
    }

    public int arrival_time;
    public int process_time;
}

class Response {
    public Response(boolean dropped, int start_time) {
        this.dropped = dropped;
        this.start_time = start_time;
    }

    public boolean dropped;
    public int start_time;
}

class Buffer {
    public Buffer(int size) {
        this.size_ = size;
        this.packetQueue = new ArrayBlockingQueue<>(size);
        this.currProcessEndTime = 0;
        this.lastProcessInBufferEndTime = 0;
    }

    public Response Process(Request request) {

        while(!packetQueue.isEmpty() && packetQueue.peek() <= request.arrival_time) {
            packetQueue.poll();
        }
        if(!packetQueue.isEmpty()){
            currProcessEndTime = packetQueue.peek();
        }

        Response response;
        if(packetQueue.offer(Math.max(lastProcessInBufferEndTime,request.arrival_time)+request.process_time)){
            response = new Response(false, Math.max(lastProcessInBufferEndTime,request.arrival_time));
            lastProcessInBufferEndTime = Math.max(lastProcessInBufferEndTime,request.arrival_time)+request.process_time;
            if(packetQueue.size() == 1)
                currProcessEndTime = lastProcessInBufferEndTime;
        }else{
            response = new Response(true, -1);
        }
        return response;
    }

    private int size_;
    private BlockingQueue<Integer> packetQueue;
    int currProcessEndTime;
    int lastProcessInBufferEndTime;
}

class ProcessPackages {
    private static ArrayList<Request> ReadQueries(Scanner scanner) throws IOException {
        int requests_count = scanner.nextInt();
        ArrayList<Request> requests = new ArrayList<Request>();
        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;
    }

    private static ArrayList<Response> ProcessRequests(ArrayList<Request> requests, Buffer buffer) {
        ArrayList<Response> responses = new ArrayList<Response>();
        for (int i = 0; i < requests.size(); ++i) {
            responses.add(buffer.Process(requests.get(i)));
        }
        return responses;
    }

    private static void PrintResponses(ArrayList<Response> responses) {
        for (int i = 0; i < responses.size(); ++i) {
            Response response = responses.get(i);
            if (response.dropped) {
                System.out.println(-1);
            } else {
                System.out.println(response.start_time);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        int buffer_max_size = scanner.nextInt();
        Buffer buffer = new Buffer(buffer_max_size);

        ArrayList<Request> requests = ReadQueries(scanner);
        ArrayList<Response> responses = ProcessRequests(requests, buffer);
        PrintResponses(responses);
    }
}

Explanation:

The inputs and outputs are stored in instances of Request and Response respectively. The processing is done by the class ProcessRequests which accepts a request each time and sends it to the Buffer one by one.

The Buffer maintains a blocking queue which only holds the request that is presently under process and those that are to be processed in future.

When a request is received, the Buffer first dequeues all the requests that have been already processed by the time this request arrives and updates the currProcessEndTime(the time by which the the first request in the queue at this moment will be processed) if possible.

It then tries adding the new packet to the queue by either adding it to the end of the non-empty queue(when there are pending requests to be processed) or to the empty queue. At the same time it also updates the variables currProcessEndTime(if this is the only request in the queue) and lastProcessInBufferEndTime(the time by which the last request in the queue will be processed). If the packet is successfully added, a response is returned with the appropriate start time. If the packet cannot be added to the queue due to lack of space, it returns a response with start time = -1.

Java collections used:

Blocking queue -

• docs.oracle.com/javase/7/docs/api/java/util..

• docs.oracle.com/javase/7/docs/api/java/util..