Найдите наименьший набор перекрывающихся заданий

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

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

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

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