Depende de qué condiciones necesiten los pasos posteriores del algoritmo. Por ejemplo, en el problema de la sala de reuniones, desea ordenar los intervalos de la reunión y luego verificar la superposición. Una forma es ordenar por tiempos de inicio, y luego recorrer la lista desde el principio, buscando reuniones que comiencen antes de que las reuniones encontradas previamente hayan terminado, eso es una superposición. O puede revertirlo, ordenar por hora de finalización, y luego recorrer la lista desde el final, buscando reuniones que finalicen antes de que las reuniones encontradas previamente hayan comenzado. Si ordena por tiempos finales y luego atraviesa desde el principio, entonces simplemente no funciona … la primera reunión que encuentre podría no ser la que comience más temprano, y se perderá la superposición.
La conclusión es que necesita diseñar y comprender el algoritmo en su conjunto, en lugar de comenzar con la idea de que necesita ordenar la lista pero no entender por qué está haciendo eso o qué hacer a continuación. Por supuesto, rara vez entendemos un algoritmo completo desde cero, por lo que en la práctica es una combinación de un enfoque de arriba hacia abajo y de abajo hacia arriba, de la misma manera que podrías jugar al ajedrez o al Sudoku: “si hago esto, ¿qué sucede?”:
“Supongamos que clasifico las reuniones por hora de inicio. ¿Eso me da una manera de determinar si se superponen? O tal vez debería ordenarlos por sus tiempos finales. ¿Eso funciona mejor? Hmm, es simétrico, así que debería poder hacerlo de cualquier manera, pero tengo que obtener los detalles correctos. Dibujemos algunos ejemplos de reuniones que se superponen, total o parcialmente en cada extremo, y veamos cómo funcionará … ”
- ¿Qué es lo contrario de 'ágil'?
- ¿Qué compañías de software han tenido que reescribir el backend de su producto porque no pudieron mantener / innovar su código existente?
- ¿Qué profesores o estudiantes están haciendo las cosas más emocionantes en aprendizaje automático e ingeniería de software en CMU?
- ¿Hay un buen libro de introducción o guía sobre cómo programar simulaciones (económicas, comerciales, físicas, etc.)?
- ¿Estudiar mecatrónica e ingeniería de software juntos te convierte en un talentoso diseñador y programador de robótica?
Entonces, ¿qué sucede cuando hacemos eso? Bueno, descubrimos que no es una gran idea ni ordenar por hora de inicio ni por hora de finalización, ya que atravesar las reuniones ordenadas por hora de inicio no nos da una buena manera de detectar la superposición: toda la idea de ordenar reuniones por una propiedad o el otro resulta estar equivocado. Lo que realmente necesitamos son todos los tiempos de inicio y finalización en orden. Así que ordena esa lista de horas, junto con si la hora es una hora de inicio o una hora de finalización. Luego recorra la lista de veces: cualquier dirección servirá, pero hagámoslo de antes a más tarde. Incremente un contador de “reunión en curso” cuando se encuentre una hora de inicio y disminuya cuando se encuentre una hora de finalización. (Esto supone que nuestra reunión db es coherente y que ninguna reunión finaliza antes de que comience). El valor máximo del contador es el número de salas de reunión necesarias.