Un amigo me dio un rompecabezas que dice que puede resolverse en un tiempo mejor que O (n ^ 3).

Dado un conjunto de n trabajos que tienen una hora de inicio y una hora de finalización establecidas (las superposiciones son muy posibles), encuentre el subconjunto más pequeño que para cada trabajo incluye ese trabajo o incluye un trabajo que se superpone con ese trabajo.

Estoy bastante seguro de que la solución óptima es elegir el trabajo con la superposición más marcada, agregarlo al conjunto de soluciones, luego marcarlo y su superposición. Y repita hasta que todos los trabajos estén marcados.
Figurar qué trabajo tiene la mayor cantidad de superposiciones sin marcar es una matriz de adyacencia simple (O (n ^ 2)), y esto tiene que rehacerse cada vez que se selecciona un trabajo, para actualizar las marcas, convirtiéndolo en O (n ^ 3).

¿Hay una mejor solución?