Calculate Completion Time for a Single-Server Reactor Queue

Problem Statement

In a low-latency trading system, an event reactor processes incoming market data packets on a single dedicated core. Packets arrive sequentially and must be processed without preemption.

You are given an integer buffer_size representing the maximum number of tasks that can wait in the incoming queue at any given moment (excluding any task currently being executed by the server). You are also given a list of tasks, where each task is represented as a pair (arrival_time, duration):

• arrival_time: The timestamp at which the task arrives at the reactor.
• duration: The amount of processing time the task requires on the server.

Rules of the reactor:

1. The server can only process one task at a time. Once started, a task runs to completion without interruption.
2. When a task arrives:
   • Any tasks that have already completed by or at arrival_time are removed from the system.
   • If the server is idle, the task begins processing immediately.
   • If the server is busy, the task enters the waiting buffer if the number of currently waiting tasks is strictly less than buffer_size.
   • If the waiting buffer is full (i.e., currently holds buffer_size waiting tasks), the incoming task is dropped immediately.
3. Tasks in the buffer are served in First-Come, First-Served (FCFS) order. Tasks arriving at the same timestamp are evaluated in the order they appear in the input list.

Return a list of integers where the i-th element is the timestamp at which task i finishes execution, or -1 if task i was dropped.

Function Signature

def calculate_completion_times(buffer_size: int, tasks: list[tuple[int, int]]) -> list[int]:
    pass

Input & Output Format

• Input:
  • buffer_size: An integer (0 <= buffer_size <= 10^5).
  • tasks: A list of tuples (arrival_time, duration) where 0 <= arrival_time <= 10^9 and 1 <= duration <= 10^9. Tasks are ordered such that arrival_time[i] <= arrival_time[i+1].
• Output: A list of integers of length len(tasks) containing the completion time of each task or -1.

Examples

Example 1

Input: buffer_size = 1, tasks = [(1, 5), (2, 4), (3, 3), (7, 2)]
Output: [6, 10, -1, 12]

Explanation:

• Task 0 arrives at t = 1, starts immediately, and finishes at t = 1 + 5 = 6.
• Task 1 arrives at t = 2. The server is busy until 6. The buffer is empty, so Task 1 enters the buffer. (Buffer size: 1/1)
• Task 2 arrives at t = 3. Server is busy until 6, and buffer already has 1 task. Task 2 is dropped (-1).
• At t = 6, Task 0 finishes. Task 1 starts immediately and finishes at t = 6 + 4 = 10. Buffer is now empty.
• Task 3 arrives at t = 7. Server is busy until 10. Buffer is empty, so Task 3 enters buffer. At t = 10, Task 3 starts and finishes at t = 10 + 2 = 12.

Example 2

Input: buffer_size = 0, tasks = [(0, 3), (2, 2), (3, 1)]
Output: [3, -1, 4]

Explanation:

• Task 0 arrives at 0 and finishes at 3.
• Task 1 arrives at 2, server is busy, buffer capacity is 0, dropped (-1).
• Task 2 arrives at 3. Task 0 finishes exactly at 3, so the server becomes idle. Task 2 starts immediately and finishes at 3 + 1 = 4.

Edge Cases

• buffer_size = 0: Tasks must find the server idle upon arrival, or they are dropped.
• Empty tasks list: Return [].
• Multiple tasks arriving at the exact same timestamp.
• Large gaps between task arrivals where the server remains idle.