А вроде она и без RMQ решается, просто порассуждать логически:
Квадрат - это не дело, но вроде не трудно заметить, что текущее кол-во подключенных пользователей общее для этих пользователей
Рассмотрим сначала упрощённый до руды вариант - пользователи только подключаются и не отключаются до самого конца – тут все тривиально (максимум будет общим для всех и равен кол-ву событий)
Теперь усложняем – сначала пользователи только подключаются, а потом только отключаются – что тут меняется? Да собственно ничего, кроме того, что надо поймать момент, когда начинаются отключения и зафиксировать «прибыль»
Ну и финальное усложнение – после одного или нескольких отключений могут снова пойти подключения… - но вроде это где-то уже было – с первого подключения после отключений по сути начинается вариант 2, т.е. надо просто фиксировать локальные максимумы для текущего множества пользователей
В итоге:
На выходе имеем словарик типа «локальный максимум : множество пользователей, для которых когда-либо был зафиксирован этот локальный максимум»
Сортируем словарик по ключам (т.е. по локальным максимумам) по убыванию и в цикле по ключам для каждого пользователя из множества под ключом проставляем максимум, равный этому ключу, предварительно выкинув из множества тех пользователей, которых мы уже видели, т.е. которым мы уже проставили максимум на предыдущих итерациях.
А вроде она и без RMQ решается, просто порассуждать логически:
Квадрат - это не дело, но вроде не трудно заметить, что текущее кол-во подключенных пользователей общее для этих пользователей
Рассмотрим сначала упрощённый до руды вариант - пользователи только подключаются и не отключаются до самого конца – тут все тривиально (максимум будет общим для всех и равен кол-ву событий)
Теперь усложняем – сначала пользователи только подключаются, а потом только отключаются – что тут меняется? Да собственно ничего, кроме того, что надо поймать момент, когда начинаются отключения и зафиксировать «прибыль»
Ну и финальное усложнение – после одного или нескольких отключений могут снова пойти подключения… - но вроде это где-то уже было – с первого подключения после отключений по сути начинается вариант 2, т.е. надо просто фиксировать локальные максимумы для текущего множества пользователей
В итоге:
На выходе имеем словарик типа
«локальный максимум : множество пользователей, для которых когда-либо был зафиксирован этот локальный максимум»
Сортируем словарик по ключам (т.е. по локальным максимумам) по убыванию и в цикле по ключам для каждого пользователя из множества под ключом проставляем максимум, равный этому ключу, предварительно выкинув из множества тех пользователей, которых мы уже видели, т.е. которым мы уже проставили максимум на предыдущих итерациях.