20. Merge Retry-Backoff Timelines

Problem

A downstream dependency (say, a webhook or a third-party lookup a voice agent calls mid-conversation) is flaky. Each failed call gets retried with exponential backoff: the first retry fires after base_delay seconds, and each subsequent retry's delay is the previous delay times multiplier, up to max_retries attempts total.

Many calls can be failing and retrying at once. Given a batch of calls that failed at different times with possibly different backoff parameters, compute the single global, chronologically ordered timeline of every retry attempt across all of them.

Source: src/20_merge_retry_backoff_timelines.py

def schedule_retries(calls: list[dict]) -> list[tuple[float, str]]: ...

# each call: {"id": str, "fail_time": float, "base_delay": float,
#             "multiplier": float, "max_retries": int}

>>> calls = [
...     {"id": "a", "fail_time": 0.0, "base_delay": 1.0, "multiplier": 2.0, "max_retries": 2},
...     {"id": "b", "fail_time": 0.5, "base_delay": 1.0, "multiplier": 2.0, "max_retries": 1},
... ]
>>> schedule_retries(calls)
[(1.0, 'a'), (1.5, 'b'), (3.0, 'a')]

Step-by-Step Approach

1. Notice each call's own sequence of retry times is already individually sorted (each delay strictly exceeds the last, since multiplier only grows the gap), which is the setup for a k-way merge, exactly like merging k sorted lists.
2. Seed a min-heap with each call's first retry attempt: (fail_time + base_delay, call_id, attempt_number=1, delay_used).
3. Repeatedly pop the earliest-timestamped attempt off the heap and append it to the output timeline — this guarantees global chronological order without ever sorting the full cross-product of attempts.
4. After popping a call's attempt, if it hasn't exhausted max_retries, compute its next delay (delay * multiplier) and push that call's next attempt back onto the heap.
5. Stop when the heap is empty (every call has exhausted its retries). Calls with max_retries = 0 should never be seeded onto the heap at all.
6. Tuple comparison in the heap naturally breaks time ties by comparing the next element (call_id), so simultaneous retries come out in id order for free.

The key insight is that you never need to materialize and sort every call's full list of retry timestamps up front — lazily generating each call's next attempt only once its previous one has been consumed keeps the heap at size O(number of still-retrying calls) instead of O(total attempts), which is the same trick that makes k-way merge of sorted lists run in O(n log k) instead of O(n log n).

Reference solution

import heapq


def schedule_retries(calls: list[dict]) -> list[tuple[float, str]]:
    # Each call's own retry attempts are already individually sorted in time
    # (each delay is strictly later than the last), so merging N calls'
    # attempt sequences is exactly the "merge k sorted lists" pattern: push
    # one candidate per call onto a heap, and every time we pop one, push
    # that same call's next attempt (if it has one left).
    by_id = {c["id"]: c for c in calls}
    heap: list[tuple[float, str, int, float]] = []  # (time, id, attempt_no, delay_used)
    for c in calls:
        if c["max_retries"] <= 0:
            continue
        delay = c["base_delay"]
        heapq.heappush(heap, (c["fail_time"] + delay, c["id"], 1, delay))

    timeline: list[tuple[float, str]] = []
    while heap:
        t, cid, attempt, delay = heapq.heappop(heap)
        timeline.append((t, cid))
        c = by_id[cid]
        if attempt < c["max_retries"]:
            next_delay = delay * c["multiplier"]
            heapq.heappush(heap, (t + next_delay, cid, attempt + 1, next_delay))
    return timeline

Key Functions & Tricks

• heapq.heappush / heapq.heappop — maintain the frontier of "next attempt per active call" in O(log k) per operation.
• Tuple ordering (time, id, attempt, delay) — sorts by time first, then breaks ties deterministically by call id.
• Lazy expansion ("push the next attempt only after popping the current one") — keeps heap size bounded by active calls, not total attempts.
• max_retries <= 0 guard — correctly excludes calls with zero allowed retries instead of seeding a phantom first attempt.

How to Recognize This Pattern