А вообще надо наверное прекальки по count посчитать

Для каждого юзера когда событие было

Амортизированная единица вроде бы

Много count у много юзеров не бывает

Хм... Интересно

Мы один раз пушим в очереди.
Мало раз достаем.
И мб перекладываем.

Так что давайте посчитаем для мелких count просто всю структуру ответов по count

Поддержка будет видимо занимать MAX_PRECALCED на register

Пушо надо подвинуть когда событие было

Просто, если в очереди для юзера 1 будет лежать момент с временем 10, а потом мы пушим момент 400 для юзера 2, то когда мы обновим очередь для юзера 1? И далее запрос на моменте времени 402.
Пусть step = 10

Ну да, мы должны слелать это в RegisterEvent.

Прикольно, если там действительно амортизированная O(1)

Значит нужна еще одна большая очередь событий, с помощью которой мы при регистрации нового события почистим мусор

Видимо мелкие, это которые меньше sqrt(N)?

Хотя не, я так не умею решать.

Короче: для плохих step я умею решать только за O(N sqrt N) в оффлайн. (Алгоритм Мо по массиву событий).

Добрый день
Наткнулся на задачу (устное собеседование ) которую не решил за время собеседования и хотел бы попрактиковать такой тип задач
на leetcode нашел похожее но и то не уверен
Примерная формулировка:

Имеется N процессов (время начала и время конца) и некоторый процессор может выполнять только K процессов за раз (K процессов могут пересекаться в смысле)
нужно оптимально вставить новый процесс в нашу очередь выполнения (тоже по сути пара (начало, конец)

с интервалами этими и проверкой пересечения запутался и написал что-то неэффективное и хотелось бы почитать про такое вот
Спасибо.

Что значит оптимально вставить?

Имел ввиду оптимальный алгоритм вставки нового процесса для выполнения

какое ограничение на N?