Оценка времени простоя запросов

Условие

Серверные ответы зачастую занимают значительно меньше времени, чем общее время, которое пользователь наблюдает на клиенте. Выяснилось, что новые запросы часто поступают, пока предыдущие ещё не завершились. Нужно измерить степень этой проблемы: вычислить суммарное время, которое запросы проводят в очереди ожидания.

В логах фиксируются два момента: момент отправки запроса в сервис и момент получения ответа, оба указаны в секундах. Записи упорядочены по возрастанию времени отправки.

Пример визуализации (секунды):

0123456789
-##.## - - - - - Запрос 1
-------##.## - - - - Запрос 2
-------------##.## Запрос 3

Для набора интервалов [(1, 4), (3, 6), (7, 9)] требуется подсчитать, сколько секунд каждый запрос ждёт, пока предыдущие не освободятся.

def balancer_error_rate(logs: list[tuple[int, int]]) -> int:
    pass

balancer_error_rate([(1, 5), (4, 7)]) # 2
balancer_error_rate([(2, 7), (5, 10)]) # 3
balancer_error_rate([(2, 7), (9, 10)]) # 0
balancer_error_rate([(2, 7), (9, 13), (10, 15)]) # 4

Функция должна вернуть суммарное время ожидания всех запросов в очереди.

Ответ

По моментам отправки и ответа нельзя точно восстановить ожидание в очереди. Примеры считают включительные пересечения секунд, а не физическую задержку; этот условный показатель можно вычислить отдельно.

Для соответствия примерам считаем, сколько целочисленных секунд текущего интервала покрыто предыдущими интервалами:

def balancer_error_rate(logs):
    latest_end = None
    total = 0
    for start, end in logs:
        if end < start:
            raise ValueError('Invalid interval')
        if latest_end is not None:
            total += max(0, min(end, latest_end) - start + 1)
        latest_end = end if latest_end is None else max(latest_end, end)
    return total

Вход отсортирован по началу. Для (1,5) и (4,7) пересечение содержит секунды 4 и 5, отсюда 2. Это метрика перекрытия, не доказанное время очереди: для настоящего ожидания нужен момент начала обработки. В непрерывном времени тот же интервал пересечения имеет длительность 1.