Daily challenge for 2026-11-01
670. Network Packet Throttle Pipeline
You are designing a rate-limiting packet processor. Incoming network packets arrive with integer arrival timestamps given by arrivals, sorted in non-decreasing order.
The system has a FIFO processing queue with a maximum capacity of limit packets. A packet arriving at timestamp t attempts to enter the queue. The queue operates as follows:
- Each packet takes exactly service_time units to process. A packet entering the queue at start time S will complete processing and leave the queue strictly at timestamp S + service_time.
- The server can process only one packet at a time. The first packet in the queue begins processing at its arrival time. Each subsequent packet starts immediately after the previous packet completes, or upon its own arrival time if the server was idle.
- When a packet arrives at time t, any packets whose completion time is less than or equal to t have already departed the queue.
- If the number of packets remaining in the queue (including the one currently being served) is strictly less than limit at time t, the packet is accepted into the queue.
- Otherwise, the queue is full and the packet is dropped.
Return the total number of packets that are successfully accepted.
Constraints:
There are 0–2,000 arrival times, sorted in non-decreasing order, including possible repeats. Times are non-negative integers at most 1,000,000. The queue limit is from 0 to 2,000, and service_time is a positive integer at most 1,000,000. Queue capacity includes the packet being served. Completion at exactly an arrival time is processed before that arrival.
Example:
Input: arrivals = [1, 2, 3, 4, 10], limit = 2, service_time = 3
Output: 4