Задачи об интервалах легко решаются перебором. Но если элементов много, то нужно сообразить в каком порядке их лучше перебирать, чтобы избежать лишних вычислений.
Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами — [начало интервала, конец интервала]. Требуется удалить минимальное число элементов, чтобы интервалы не перекрывали друг друга.
Исходя из формулировки, задача выглядит так, что требуется подсчитать число перекрытий для каждого интервала, и далее начать удаление с тех элементов, у которых больше всего перекрытий, актуализируя число перекрытий для оставшихся элементов.
Сложность вычислений превосходит N*N, т.к. придется каждый элемент сравнивать с другим, а потом пройтись по части списка, удаляя элементы и актуализируя число перекрытий, что тоже может составить до N*N операций.
Обсуждение подхода
Сложность высока из-за того, что элементы не упорядочены. Мы вынуждены проверять отношения все ко всем.
Если отсортировать элементы по возрастанию левой границы, то нам уже как минимум не придется сравнивать каждый элемент со всеми предыдущими по левой границе. Останется анализ правой границы.
Если два интервала пересекаются, нам нужно выбрать какой из них удалить. Т.к. речь идет о сравнении по правой границе, то логично удалить тот интервал, который имеет меньшую правую границу, т.к. это более вероятно позволит избежать пересечения с последующими в списке интервалами.
Мы можем отслеживать значение левой границы, двигаясь по списку интервалов, чтобы сразу определять — имеется ли пересечение с следующим рассматриваемым интервалом. Если пересечения нет, то границу можно отодвигать по правой границе нового интервала.
Если же пересечение есть, то мы должны решить — удалять рассматриваемый интервал или один из предыдущих. Удаляется тот, у которого правая граница больше.
Реализация
Код на TS/JS:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
function eraseOverlapIntervals(intervals: number[][]): number { // отслеживаем левую границу пересечений let leftBorder = -Infinity, count = 0; // сортировка интервалов по левой границе intervals.sort((a,b) => a[0] - b[0]) // просматриваем отсортированный список for (let i = 0; i < intervals.length; i ++) { const [left, right] = intervals[i] if (leftBorder <= left) { // если текущий интервал не пересекается leftBorder = right } else { // при пересечении решаем какой интервал // будет удален count ++ if (right < leftBorder) { let j = i - 1 while (intervals[j][1] < leftBorder) j -- // я не удаляю элемент из массива, // т.к. это затратная операция, // а просто сбрасываю правую границу intervals[j][1] = -Infinity; leftBorder = intervals[i][1] } else { intervals[i][1] = -Infinity; } } } return count; }; |
Сложность вычислений можно оценить как N * log(N) — это неизбежный вклад сортировки, и далее порядка 2 * N — перебор сортированного массива.
