Se puede demostrar que en una solución óptima hay al menos un segmento el cual no se mueve de lugar. Por lo que se puede fijar cual va a ser este segmento y arreglar los otros teniendo en cuenta este, es decir si se ordenan los segmentos (por inicio, por ejemplo) y el segmento fijado es ~s_i~ entonces los segmentos ~s_1, s_2, \ldots, s_{i-1}~ irían a la izquierda de ~s_i~ y los segmentos ~s_{i + 1}, s_{i + 2}, \ldots, s_n~ irían a la derecha, lo que se deben correr estos segmentos para que queden sin espacios entre ellos, este proceso se puede hacer en ~O(n)~ por lo que en total la complejidad sería ~O(n^2)~.

También si se usa tablas acumulativas se puede calcular todo esto en ~O(n)~.

Complejidad: ~O(n^2)~.

Bonus: Demostrar que el segmento a mantenerse fijo es la mediana de los segmentos (el que queda en el medio al ordenar).