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

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

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

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

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

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

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

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

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

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

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

Реализация

Код на TS/JS:

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

Написать комментарий

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

Задача о наибольшей сумме монет

Апрель 15, 2023 г.

Решаем задачу № 2218 с leetcode - Maximum Value of K Coins From Piles. В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да - суть именно такая. У нас есть стопки монет, и дано число ...

Читать

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать

 

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

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



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