16. Jitter Buffer Reordering with a Playback Deadline

Problem

Audio packets sent over a real-time connection don't always arrive in the order they were generated — network jitter can reorder or delay them. A jitter buffer holds a small window of recently-arrived packets so it can release them for playback in the correct sequence, but it can't wait forever for a straggler.

Once too many later packets have piled up waiting on one missing earlier packet, the buffer gives up on it, marks that slot lost, and moves on so the rest of the stream doesn't stall. Given the arrival order of sequence numbers (with gaps for packets that never show up at all), a total count, and a buffering capacity, reconstruct the full playback timeline.

Source: src/16_jitter_buffer_reorder.py

def reorder_jitter_buffer(arrivals: list[int], total: int, capacity: int) -> list[int | None]:
    ...

Examples:
>>> reorder_jitter_buffer([0, 2, 1, 3], 4, 2)
[0, 1, 2, 3]

>>> reorder_jitter_buffer([1, 2, 4, 5], 6, 2)
[None, 1, 2, None, 4, 5]

Step-by-Step Approach

1. Maintain a min-heap of arrived-but-not-yet-released sequence numbers, and an expected counter starting at 0 — the next seq the playback timeline needs.
2. On each arrival, push it onto the heap, then drain: while the heap's smallest value equals expected, pop it, append it to the output, and increment expected. This handles runs of consecutive packets releasing at once.
3. After draining, check whether the heap has grown past capacity. If so, the buffer has waited long enough: append None for the stalled expected seq, increment expected, and re-run the drain step in case that unblocked something already buffered.
4. Repeat the overflow check in a loop (not just once) — dropping one seq can still leave the heap over capacity, or can immediately unblock several buffered releases.
5. Once every arrival has been processed, flush what's left: while expected < total, release it from the heap if it's the current minimum, otherwise mark it lost, and advance.
6. Handle the edges: an empty arrivals list flushes straight to all-None, and a capacity of 0 still works correctly for packets that happen to arrive in order, because the drain step runs before the overflow check.

The key insight is separating two independent loops — a heap drain that fires whenever the next expected packet becomes available, and a capacity-triggered eviction that only fires when buffering has gone on too long — rather than trying to track wall-clock deadlines directly.

Reference solution

import heapq


def reorder_jitter_buffer(arrivals: list[int], total: int, capacity: int) -> list[int | None]:
    heap: list[int] = []  # min-heap of arrived-but-not-yet-released seq numbers
    output: list[int | None] = []
    expected = 0
    for seq in arrivals:
        heapq.heappush(heap, seq)
        # release every buffered packet that's next in line
        while heap and heap[0] == expected:
            output.append(heapq.heappop(heap))
            expected += 1
        # buffer overflowed: give up on the stalled expected seq(s) and keep draining
        while len(heap) > capacity:
            output.append(None)
            expected += 1
            while heap and heap[0] == expected:
                output.append(heapq.heappop(heap))
                expected += 1
    # end of stream: resolve any seq numbers that were still pending or never arrived
    while expected < total:
        if heap and heap[0] == expected:
            output.append(heapq.heappop(heap))
        else:
            output.append(None)
        expected += 1
    return output

Key Functions & Tricks

• heapq.heappush / heapq.heappop — O(log capacity) insert and extract-min for tracking the smallest buffered seq.
• Drain-then-evict ordering — always try to release in-order packets before considering a forced drop, so exact-order arrivals never pay an eviction cost even at capacity 0.
• while heap and heap[0] == expected — releases every consecutive ready packet in one pass, not just one per arrival.
• while len(heap) > capacity — a loop, not an if, because a single drop can still leave the buffer over budget or can cascade into further releases.
• Final flush loop — resolves every remaining expected slot up to total, covering packets that never arrived at all as well as ones still stuck in the heap.

How to Recognize This Pattern