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

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

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

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

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

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

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

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

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

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

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

Реализация

Код на TS/JS:

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

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

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

Задача: подсчета кол-ва возможных маршрутов

Июнь 25, 2023 г.

Решаем задачу с литкода №1575 Count All Possible Routes. Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым ...

Читать

Декодировка строки

Апрель 30, 2023 г.

Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными. Чтобы выработать решение, рассмотрим пример: [crayon-6afd1a3d6352b964588246/] ...

Читать

87. Scramble string - задача о перетасованных строках

Март 30, 2023 г.

Решаем задачу с литкода о перетасовке строки. Даны две строки, нужно определить является ли вторая строка результатом перетасовки букв в первой. Правила ...

Читать
 

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

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



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