15. Adaptive Quality Selection Under a Rolling Bandwidth Budget

Problem

A streaming audio client picks, at each measurement interval, the highest quality tier it can sustain without exceeding currently available bandwidth — the same kind of tradeoff a real-time TTS client would need to make between output quality and staying ahead of playback.

Given a sorted list of quality tier bitrates and a stream of bandwidth samples, return, for each sample, the index of the highest tier whose bitrate fits within that sample — or -1 if even the smallest tier doesn't fit.

Source: src/15_adaptive_bitrate_selector.py

def select_quality_tiers(bandwidth_kbps: list[int], tier_bitrates: list[int]) -> list[int]:

>>> select_quality_tiers([50, 120, 30, 200], [32, 64, 128, 256])
[0, 1, -1, 2]

>>> select_quality_tiers([256, 256], [32, 64, 128, 256])
[3, 3]

Step-by-Step Approach

1. Notice tier_bitrates is already sorted ascending — that's the cue to binary search instead of linear-scanning the tier list for every bandwidth sample.
2. For each bandwidth sample bw, you want the index of the rightmost tier whose bitrate is <= bw. Python's bisect.bisect_right(tier_bitrates, bw) gives the insertion point just past every tier <= bw.
3. Subtract 1 from that insertion point to land on the actual index of the highest affordable tier.
4. This subtraction also handles the "nothing fits" case for free: if bw is smaller than every tier, bisect_right returns 0, and 0 - 1 == -1 is exactly the sentinel the problem wants — no separate branch needed.
5. Repeat per sample and collect the results; each lookup is O(log t) where t is the number of tiers, so the whole pass is O(n log t) instead of O(n · t) for a linear scan per sample.

The key insight is that "pick the largest sorted value <= x" is exactly what bisect_right(...) - 1 computes, and that the same expression's edge behavior (returning -1 when nothing qualifies) happens to line up with the problem's own sentinel value, eliminating what would otherwise be a separate bounds check.

Reference solution

import bisect


def select_quality_tiers(bandwidth_kbps: list[int], tier_bitrates: list[int]) -> list[int]:
    result = []
    for bw in bandwidth_kbps:
        # bisect_right gives the insertion point just past any tiers <= bw;
        # subtracting 1 lands on the highest affordable tier's index, or -1
        # naturally if even the smallest tier exceeds bw. O(log t) per sample.
        idx = bisect.bisect_right(tier_bitrates, bw) - 1
        result.append(idx)
    return result

Key Functions & Tricks

• bisect.bisect_right(a, x) — returns the insertion point after any existing entries equal to x, i.e. how many elements of the sorted list are <= x.
• bisect_right(...) - 1 — converts that count directly into the index of the largest element <= x, with -1 as the natural "none qualify" result.
• sorted tier_bitrates precondition — is what makes binary search valid at all — the pattern breaks silently on unsorted input.

How to Recognize This Pattern