Друг дал мне загадку, которую, по его словам, можно решить быстрее, чем за O (n ^ 3) времени.

Учитывая набор из n заданий, каждое из которых имеет заданное время начала и время окончания (возможны перекрытия), найдите наименьшее подмножество, которое для каждого задания либо включает это задание, либо включает задание, которое перекрывается с этим заданием.

Я почти уверен, что оптимальным решением будет выбрать задание с самым непомеченным перекрытием, добавить его в набор решений, затем отметить его и перекрытие. И повторяйте, пока все работы не будут отмечены.
Выяснение того, какое задание имеет наиболее неотмеченные перекрытия, представляет собой простую матрицу смежности (O (n ^ 2)), и ее нужно переделывать каждый раз, когда задание выбирается, чтобы обновить отметки, делая его O (n ^ 3). ).

Есть ли лучшее решение?