Задача о неперекрывающихся интервалах

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

Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами — [начало интервала, конец интервала]. Требуется удалить минимальное число элементов, чтобы интервалы не перекрывали друг друга.

Исходя из формулировки, задача выглядит так, что требуется подсчитать число перекрытий для каждого интервала, и далее начать удаление с тех элементов, у которых больше всего перекрытий, актуализируя число перекрытий для оставшихся элементов.

Сложность вычислений превосходит N*N, т.к. придется каждый элемент сравнивать с другим, а потом пройтись по части списка, удаляя элементы и актуализируя число перекрытий, что тоже может составить до N*N операций.

Обсуждение подхода

Сложность высока из-за того, что элементы не упорядочены. Мы вынуждены проверять отношения все ко всем.

Если отсортировать элементы по возрастанию левой границы, то нам уже как минимум не придется сравнивать каждый элемент со всеми предыдущими по левой границе. Останется анализ правой границы.

Если два интервала пересекаются, нам нужно выбрать какой из них удалить. Т.к. речь идет о сравнении по правой границе, то логично удалить тот интервал, который имеет меньшую правую границу, т.к. это более вероятно позволит избежать пересечения с последующими в списке интервалами.

Мы можем отслеживать значение левой границы, двигаясь по списку интервалов, чтобы сразу определять — имеется ли пересечение с следующим рассматриваемым интервалом. Если пересечения нет, то границу можно отодвигать по правой границе нового интервала.

Если же пересечение есть, то мы должны решить — удалять рассматриваемый интервал или один из предыдущих. Удаляется тот, у которого правая граница больше.

Реализация

Код на TS/JS:

Сложность вычислений можно оценить как N * log(N) — это неизбежный вклад сортировки, и далее порядка 2 * N — перебор сортированного массива.

Мало букафф? Читайте есчо !

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать

TS: функция преобразования к каноническому пути

Март 15, 2023 г.

Увидел эту задачу на leetcode - https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS. Задача ...

Читать

Поиск выхода из лабиринта

Июнь 3, 2023 г.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так - дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, ...

Читать

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи. Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов. ...

Читать
 

Комментарии к «Задача о неперекрывающихся интервалах»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: