Начало + конец дано - сколько «транзакций» одновременно

Question

У меня есть пара данных, которые включают начало транзакции и ее конец в формате DateTime. Я хочу выяснить, сколько транзакций выполняется одновременно. Есть ли алгоритм, который мог бы решить мою проблему?

Answer 1

Если у вас есть список «начинается» и «заканчивается», и вы хотите знать максимальное количество одновременно открытых соединений (или в каждой точке, сколько соединений открыто), я бы сделал следующее (в псевдокоде ):

1. Поместите каждое из «начинается» и «заканчивается» в структуру данных с отметкой времени и другим полем, значение которого будет +1 для начала и -1 для конца
2. Поместите все эти элементы в массив и отсортируйте их по отметке времени
3. Создайте еще один массив, который в каждой записи имеет сумму + 1 с и -1 с от предыдущего массива до этого индекса
4. Максимальное значение этого массива - ваш ответ

Пример:

Input: 

Connection A opened at 1 closed at 3
Connection B opened at 2 closed at 6
Connection C opened at 4 closed at 7
Connection D opened at 5 closed at 8

Create the following structure:

Timestamp:           1  2  3  4  5  6  7  8
First array sorted: +1 +1 -1 +1 +1 -1 -1 -1 
Second array:        1  2  1  2  3  2  1  0

Max open connections = 3
Number of connections open at timestamp 6 = 2

Второй массив подсчитывает количество одновременно открытых соединений в каждой временной метке и рассчитывается следующим образом (псевдокод):

second_array[i] = sum(first_array[1..i])