27. Merge K Sorted Latency Logs

Problem

Cartesia's real-time voice pipeline runs many parallel GPU workers, each emitting its own internally time-ordered log of (timestamp, latency_ms) samples for the requests it served. For a unified operational view, ops tooling needs one global timeline: merge k separately-sorted per-worker logs into a single list sorted ascending by timestamp, without concatenating everything and re-sorting from scratch.

Each inner list is one worker's log, already sorted ascending by timestamp. Ties are broken by the originating log's position in the input (earlier logs win). The whole thing must run in O(n log k) time via a k-way heap merge, not the naive O(n log n) full sort.

Source: src/27_merge_k_latency_logs.py

def merge_latency_logs(logs: list[list[tuple[float, float]]]) -> list[tuple[float, float]]: ...

>>> merge_latency_logs([[(1.0, 120.0), (3.0, 95.0)], [(2.0, 150.0)]])
[(1.0, 120.0), (2.0, 150.0), (3.0, 95.0)]
>>> merge_latency_logs([[(0.5, 80.0)], [], [(0.2, 60.0), (0.9, 70.0)]])
[(0.2, 60.0), (0.5, 80.0), (0.9, 70.0)]

Step-by-Step Approach

1. Recognize that each of the k logs is already individually sorted — the only work left is interleaving them, which is exactly what a k-way merge (the merge step of merge sort, generalized past k=2) is built for.
2. Seed a min-heap with the first entry of every non-empty log, keyed by (timestamp, log_idx, entry_idx). Including the log and entry index in the key means the heap never has to compare the latency values themselves, and ties on timestamp resolve deterministically by log order.
3. Pop the smallest entry from the heap — it is guaranteed to be the next-earliest timestamp not yet emitted, because every log is sorted and every log's unconsumed head is currently represented in the heap.
4. Append that popped entry to the result list.
5. Push that log's next entry onto the heap, if it has one — this keeps every non-exhausted log represented by exactly one heap entry at all times.
6. Repeat until the heap is empty; the result list is the fully merged, globally sorted timeline.

The key insight is that at any point in the merge, the true next-smallest element overall must be the smallest among the current heads of the k logs — you never need to look further into any log than its current head, which is what bounds the work to O(n log k) instead of O(n log n).

Reference solution

import heapq


def merge_latency_logs(logs: list[list[tuple[float, float]]]) -> list[tuple[float, float]]:
    # Seed the heap with each non-empty log's first entry. Heap keys are
    # (timestamp, log_idx, entry_idx) -- log_idx breaks timestamp ties by log
    # order, entry_idx makes every key unique so latency (a float) is never
    # compared, which would be wasted work and a subtle bug risk.
    heap: list[tuple[float, int, int, float]] = []
    for log_idx, log in enumerate(logs):
        if log:
            ts, lat = log[0]
            heapq.heappush(heap, (ts, log_idx, 0, lat))

    result: list[tuple[float, float]] = []
    while heap:
        ts, log_idx, entry_idx, lat = heapq.heappop(heap)
        result.append((ts, lat))
        # advance that log's pointer and push its next entry, if any
        next_idx = entry_idx + 1
        if next_idx < len(logs[log_idx]):
            next_ts, next_lat = logs[log_idx][next_idx]
            heapq.heappush(heap, (next_ts, log_idx, next_idx, next_lat))
    return result

Key Functions & Tricks

• heapq.heappush / heapq.heappop — O(log k) heap operations, where k is the number of active logs (heap size never exceeds k).
• Composite key (timestamp, log_idx, entry_idx) — makes every heap entry's sort key unique, so Python never falls through to comparing the latency floats.
• One heap entry per active log — the invariant that keeps the heap size bounded by k rather than n.
• enumerate(logs) — pairs each log with its index for the tie-break key during seeding.
• Advancing a log's pointer only after its current head is popped — ensures no entry is ever considered before its predecessor in the same log.

How to Recognize This Pattern