Début et fin donnés - combien de "transactions" en même temps ?

Question

J'ai un couple de données, qui comprend le début d'une transaction et sa fin dans un format DateTime. Je veux savoir combien de transactions sont en cours en même temps. Existe-t-il un algorithme qui pourrait résoudre mon problème ?

Answer 1

Si vous avez une liste de "débuts" et de "fins", et que vous voulez connaître le nombre maximum de connexions ouvertes simultanément (ou à chaque point combien de connexions sont ouvertes), je ferais ce qui suit (en pseudo-code) :

1. Placez chacun des "débuts" et des "fins" dans une structure de données avec l'horodatage et un autre champ dont la valeur sera +1 pour le début et -1 pour la fin.
2. Mettez tous ces éléments dans un tableau, et triez-le par horodatage.
3. Créez un autre tableau dont chaque entrée contient la somme des +1 et des -1 du tableau précédent jusqu'à cet indice.
4. La valeur maximale de ce tableau est votre réponse

Exemple :

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

Le deuxième tableau compte le nombre de connexions ouvertes simultanément dans chaque horodatage, et est calculé comme suit (pseudo-code) :

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