Implement Dynamic (Static-Window) Request Batching

The problem, from first principles

Processing one request at a time under-utilizes an accelerator (GPUs are efficient at large matmuls, not many tiny ones); waiting to accumulate a large batch before running anything hurts latency for early-arriving requests. Implement a dynamic (static-window) batching policy: incoming requests are grouped into a batch either once max_batch_size requests have arrived, or once max_wait_time has elapsed since the oldest currently-waiting request arrived — whichever happens first.

From theory to code

close_time = min(t0 + max_wait_time, time at which the batch reaches max_batch_size)

where t0 is the oldest unbatched request's arrival time.

Constraints

• Process arrivals in chronological order (already sorted by arrival time).
• A batch closes (and a new one starts) the instant it reaches max_batch_size.
• If a batch hasn't reached max_batch_size, it closes at batch_start_time + max_wait_time even if a new request would otherwise have joined later.
• Return the list of batches (each a list of request ids) and each batch's close time.

Hints