Найти временной интервал с максимальным количеством параллельных процессов

Question

Система генерирует журналы в формате: startTime, endTime, Request. Как рассчитать интервал с максимальным количеством одновременных запросов? Я пробовал использовать hashmap с отметкой времени в качестве значения запроса ключа как значение. Заполнять ключи со всеми значениями между началом и временем для каждого запроса и счетчика обновлений, но это потребует огромного пространства, если метка времени точно до миллисекунд.

Answer 1

Преобразовать список событий со свойствами ц, значение

начальное время: 123456, EndTime: 23456, запрос: .... становится два события:

(123456, 1) (23456, -1)

Теперь у вас будет 2x количество запросов в качестве событий.

Если вы сортируете эти события по метке времени, вы можете перебирать их, добавляя и вычитая значения. Следите за наибольшим значением, которое вы видели, и меткой времени, в которой он произошел.

Это работает в O (nlogn), так как вам нужно сортировать события и принимать O (n) пространство.