Latency budget queries
Your task
A load test sweeps one service at a rising set of client counts. concurrency is strictly increasing and latency_ms holds the p99 measured at each of those counts, in the same order. Warm parallelism pulls the curve down to a single low point and contention pushes it back up, so latency_ms falls strictly to its minimum and rises strictly after it, and no two neighbouring readings are equal. Either side may be empty. For every entry of budget_ms return the largest client count whose p99 is at or below that budget, or -1 when no setting qualifies, in query order. Both lists are long, so rereading the sweep per query is too slow, and the readings are not sorted, so a plain bisect over them lands on the wrong side.
Examples
highest_safe_concurrency(concurrency: list[int], latency_ms: list[int], budget_ms: list[int]) -> list[int]Example 1
Input
highest_safe_concurrency([1, 2, 4, 8, 16, 32], [90, 60, 41, 55, 120, 400], [50, 41, 40, 400])Output
[4, 4, -1, 32]Example 2
Input
highest_safe_concurrency([5, 10, 15], [30, 20, 25], [25, 19])Output
[15, -1]Example 3
Input
highest_safe_concurrency([2, 4, 6, 8, 10], [50, 30, 10, 30, 50], [10, 30, 50, 9, 51])Output
[6, 8, 10, -1, 10]