0x7b - Mínimo número de salones para acomodar todas las clases

Una universidad está planeando su horario. La universidad cuenta con la hora de inicio y fin de todas las clases del día, y necesita saber cuál es el mínimo número de salones necesarios para dictarlas.

En un salón de clase sólo puede dictarse una clase a la vez. Sin embargo, está permitido que una nueva clase comience justo en el mismo instante que la clase anterior termina.

Por ejemplo, supongamos que ésta es la lista de horas y clases que la universidad necesita dictar en el día:

• Estructuras de datos y algoritmos: 10:00 a 12:00
• Sistemas operativos: 11:00 a 12:30
• Lenguajes formales y compiladores: 15:00 a 18:00
• Bases de datos: 12:30 a 13:30
• Matemáticas discretas: 13:30 a 14:30
• Matemáticas indiscretas: 15:30 a 19:00

Es posible acomodar estas clases en sólo dos salones de clases, de la siguiente manera:

Salón #1:

• 10:00 a 12:00: Estructuras de datos y algoritmos
• 13:30 a 14:30: Matemáticas discretas
• 15:00 a 18:00: Lenguajes formales y compiladores

Salón #2:

• 11:00 a 12:30: Sistemas operativos
• 12:30 a 13:30: Bases de datos
• 15:30 a 19:00: Matemáticas indiscretas

Por otra parte, en este caso es imposible usar un solo salón para dictar todas las clases, porque Estructuras de datos y algoritmos y Sistemas operativos estarían en conflicto. Por lo tanto, dos es el mínimo de salones necesarios.

Escribe un programa que dada la lista de clases, calcula el mínimo número de salones necesarios para acomodar todas las clases sin conflictos.

Entrada

La entrada contiene varias líneas:

• La primera línea contiene N, el número de clases en el día.
• Luego vienen N líneas, cada una con una clase. Cada clase está descrita por su hora de inicio y fin en formato HH:MM, separados por un espacio. Está garantizado que la hora de inicio es estrictamente menor a la hora de fin (en otras palabras, todas las clases empiezan antes de que terminen y duran por lo menos un minuto).

Salida

La salida debe tener una única línea con el mínimo número de salones necesarios para dictar las clases.

Entrada de ejemplo #1

6
10:00 12:00
15:00 18:00
11:00 12:30
12:30 13:30
13:30 14:30
15:30 19:00

Salida de ejemplo #1

2

Explicación del ejemplo #1

Este es el ejemplo explicado en el enunciado del problema.

Entrada de ejemplo #2

2
10:00 12:00
10:00 12:00

Salida de ejemplo #2

2

Explicación del ejemplo #2

Es posible que haya dos clases con exactamente el mismo horario. En este caso necesitamos ponerlas en dos salones separados.

Entrada de ejemplo #3

2
10:00 12:00
12:00 13:00

Salida de ejemplo #3

1

Explicación del ejemplo #3

Podemos acomodar ambas clases en el mismo salón, una después de otra.

Entrada de ejemplo #4

2
10:00 12:30
12:00 13:00

Salida de ejemplo #4

2

Explicación del ejemplo #4

En este caso nos vemos forzados a usar dos salones porque hay un conflicto de 12:00 a 12:30.

Entrada de ejemplo #5

2
10:00 12:01
12:00 13:00

Salida de ejemplo #5

2

Explicación del ejemplo #5

En este caso el conflicto es de sólo un minuto pero el profesor de la primera clase se niega a terminar un minuto más temprano, entonces nos vemos forzados a usar dos salones.

Entrada de ejemplo #6

5
08:00 19:00
09:00 15:00
10:30 22:45
12:00 12:30
12:15 23:00

Salida de ejemplo #6

5

Explicación del ejemplo #6

Todas las clases están en conflicto con todas las demás, entonces necesitamos ponerlas todas en salones separados.

Entrada de ejemplo #7

5
00:00 23:59
00:00 23:59
08:00 09:00
09:00 10:00
10:00 11:00

Salida de ejemplo #7

3

Explicación del ejemplo #7

Usamos un salón para cada uno de las clases que duran todo el día y un salón para las otras tres clases restantes.

Restricciones

• Está garantizado que 1 ≤ N ≤ 100,000.

Envía tu solución