Network Packet Buffer Simulator

Scheduling Simulation Queue

Problem Description

In this problem, you will simulate the processing of network packets by a router that has a limited buffer size.

Details

  • The router has a buffer capable of holding a maximum of S packets at any given time.
  • Packets arrive in order. Each packet has an arrival time and a processing time.
  • When a packet arrives:
    • If there is room in the buffer, it is enqueued and will be processed in order of arrival.
    • If the buffer is full, the packet is dropped and no further processing occurs for that packet.
  • The router processes one packet at a time. When the router is idle, it starts processing the next packet immediately if one is waiting in the buffer.
  • If a packet arrives and the router is idle, its processing starts at its arrival time. Otherwise, it starts when the previous packet has finished processing.

Your task is to determine, for each packet, the time at which processing of that packet starts, or output -1 if the packet is dropped.

Input Format

  • The first line contains two integers: S (the size of the buffer) and N (the number of packets).
  • Each of the following N lines contains two integers: the arrival_time and the processing_time of the packet.

Output Format

For each packet in the order of arrival, output a single integer:

  • The start time of its processing if the packet is processed, or
  • -1 if the packet is dropped.

Example

For a buffer size of 1 and 3 packets given as follows:

1 3
0 2
1 4
5 3

The expected output would be:

0
-1
5

In this example:

  • The first packet arrives at time 0 and starts processing immediately, taking 2 time units (finishing at time 2).
  • The second packet arrives at time 1 when the buffer is full and is therefore dropped.
  • The third packet arrives at time 5 (when the router is idle) and starts processing at time 5.

Constraints

  • 0 ≤ arrival_time ≤ 10^5
  • 0 < processing_time ≤ 10^3
  • 0 < S, N ≤ 10^5

Implement your solution in any language of your choice. Make sure your program is efficient and can handle large inputs.

Good luck!