¿Algoritmo para encontrar la mitad del mayor espacio de tiempo libre en el período?

Digamos que quiero programar una recopilación de eventos en el período 00: 00–00: 59. Los programo en minutos completos (00:01, nunca 00:01:30).

Quiero separarlos lo más lejos posible dentro de ese período, pero no sé de antemano cuántos eventos tendré en total dentro de esa hora. Puedo programar un evento hoy, luego dos más mañana.

Tengo el algoritmo obvio en mi cabeza, y puedo pensar en formas de fuerza bruta para implementarlo, pero estoy seguro de que alguien conoce una forma más agradable. Prefiero Ruby o algo que pueda traducir a Ruby, pero tomaré lo que pueda obtener.

Así que el algoritmo que puedo pensar en mi cabeza:

El evento 1 acaba a las 00:00.

El evento 2 termina a las 00:30 porque ese momento es el más alejado de los eventos existentes.

El evento 3 podría terminar a las 00:15 o a las 00:45. Así que tal vez elijo el primero, 00:15.

El evento 4 termina en 00:45.

El evento 5 termina en algún lugar alrededor de 00:08 (redondeado desde 00:07:30).

Y así.

Así que podríamos ver cada par de minutos tomados (por ejemplo, 00: 00–00: 15, 00: 15–00: 30, 00: 30–00: 00), elegir el rango más grande (00: 30–00: 00) ), dividirlo por dos y redondearlo.

Pero estoy seguro de que se puede hacer mucho mejor. ¡Comparte!