Алгоритм проверки, можно ли найти (перекрывающиеся) интервалы для покрытия большего интервала

Question

Предположим, вам дан список интервалов.Предположим, что мы каким-то образом можем задать каждому интервалу, каковы его начало и конец (например, list.get (i) .getStart () и list.get (i) .getEnd ()).В дополнение к списку вам дается начальное целое и конечное целое число.Я хочу знать, могут ли быть найдены некоторые интервалы из этого списка, чтобы покрыть наш «домен-интервал» [начало, конец].

Пример:

Input: list{[1,5],[2,7],[7,9]}, start: 1, end: 9; 
Output: TRUE.

But the same list with start 0 and end 9, will result in FALSE.

Теперь мне интересно, как я мог бы сделать это эффективно.Подсказки (или ответы) приветствуются!

Спасибо.

Answer 1

Откажитесь от интервалов, которые заканчиваются до вашего начала или начинаются после вашего конца.В вашем примере таких интервалов нет, но если бы [-3,0] или [11,17] были там, они были бы отброшены.Сортировать оставшиеся интервалы по началу.Насколько это возможно, объедините оставшиеся интервалы в более крупные интервалы.Таким образом, [1,5],[2,7] сначала объединяются в [1,7], который, в свою очередь, соединяется с [7,9] для формирования [1,9].Если полученный интервал покрывает интервал вашего домена, ответ был да.

Насколько я понимаю, ваш список будет охватывать start: 1, end: 9, я не знаю, почему вы ожидаете false.