Pista 1

Observa que todos los niños de una misma escuela siempre permanecen juntos en la fila.

Pista 2

En lugar de manejar la fila niño por niño, se puede manejar una fila de escuelas.

Solución

La fila puede verse como una fila de escuelas. Para cada escuela \(E\) se mantiene una cola con los identificadores de sus niños, y además una cola que almacena el orden en que aparecen las escuelas en la fila.

Cuando ocurre un evento \(L\; ID\; E\), si la escuela \(E\) no está actualmente en la fila, se agrega al final de la cola de escuelas. Luego, el identificador \(ID\) se inserta al final de la cola correspondiente a la escuela \(E\), quedando automáticamente detrás del último niño de su escuela.

Cuando ocurre un evento \(R\), se atiende al niño perteneciente a la escuela que está al frente de la cola de escuelas. Se imprime su identificador \(ID\) y se elimina de su cola. Si dicha cola queda vacía, la escuela \(E\) se elimina de la fila.

Implementación en C++

La_fila_de_la_posada_de_Don_Liborio.cpp

Complejidad

• Usando unordered_map, cada evento se procesa en tiempo \(O(1)\) amortizado.
• La complejidad total es \(O(N)\) en tiempo y \(O(N)\) en memoria.
• Si se utiliza map, las operaciones del mapa toman \(O(\log N)\), por lo que la complejidad total pasa a ser \(O(N \log N)\).