Su código esencialmente calcula el intervalo que se superpone con el número máximo de otros intervalos (eso también, con errores). Eso no es lo que se ha pedido en este problema y, por lo tanto, obtiene una respuesta incorrecta.
La pregunta real que se ha hecho es encontrar el punto de tiempo que cae en el número máximo de intervalos . Este problema se puede resolver de manera más fácil.
Supongamos que hay un contador en la habitación, inicialmente establecido en cero. Cada vez que alguien entra en la habitación, incrementamos el contador en uno y cada vez que alguien se va, lo decrementamos. Naturalmente, el contador indica el número de personas en la habitación en cada momento. El valor máximo alcanzado por el contador es la respuesta que queremos.
- ¿Debo aprender algoritmos y estructuras de datos de cada lenguaje de programación?
- C: ¿Existe un enfoque general para convertir una función recursiva en iterativa y viceversa?
- ¿Cuál sería un buen método o algoritmo para predecir el ganador de una carrera de caballos, dada una gran cantidad de información sobre las carreras de caballos?
- ¿Cómo debo codificar el algoritmo en Python?
- ¿Cuál es la complejidad temporal del algoritmo babilónico para encontrar la raíz cuadrada?
Podemos simular el contador fácilmente. Ordene los puntos finales de todos los intervalos, recordando si cada punto final es el izquierdo o el derecho. Pon el contador a cero. Ahora escanee la matriz ordenada de izquierda a derecha. Cada vez que se encuentre un punto final izquierdo de un intervalo, incremente el contador y cada vez que se encuentre un punto final derecho, disminuya. Simplemente envíe el valor máximo alcanzado por el contador como la respuesta. La solución se ejecuta en O (N log N).
Problemas como este que involucran intervalos aparecen a menudo en concursos de programación. Muchas veces, ordenar los puntos finales de los intervalos por separado como lo hicimos aquí ayuda a encontrar la respuesta.
