m amigo me deu um quebra-cabeça que ele diz que pode ser resolvido em um tempo melhor que O (n ^ 3

Dado um conjunto de n trabalhos em que cada um tem uma hora de início e um término definidos (sobreposições são muito possíveis), encontre o menor subconjunto que para cada trabalho inclui esse trabalho ou inclui um trabalho que se sobrepõe a esse trabalh

Tenho certeza de que a solução ideal é escolher o trabalho com a sobreposição mais desmarcada, adicioná-lo ao conjunto de soluções, marcá-lo e sua sobreposição. E repita até que todos os trabalhos sejam marcado
A definição de qual trabalho tem os overlappers mais não marcados é uma matriz de adjacência simples (O (n ^ 2)), e isso deve ser refeito sempre que um trabalho é selecionado, a fim de atualizar as marcas, tornando-o O (n ^ 3).

Existe uma solução melhor