Трюки для решения проблем слияния/вставки/пересечения интервалов

Зачем нам нужно решать интервальные задачи?

Интервальные задачи вообще важны в мире программирования. Интервалы могут быть либо периодом времени, либо диапазоном чисел. Это ключевые элементы планирования задач. Есть много популярных проблем планирования: как позволить клиентам бронировать столик в ресторане без конфликтов? Как планировать ресурсы на процессоре? Как назначить класс учителям? Поэтому существует множество проблем Leetcode, связанных с интервальными операциями.

1. Понимание основных интервальных отношений

Интервальных отношений не так много. Если вы четко их понимаете, вы сможете легко реализовать и решить проблемы, связанные с интервалами. Скажем, если у нас есть 2 интервала A и B, каковы возможные отношения между ними?

Очевидно, у нас есть только 3 возможных случая между двумя интервалами A и B: отсутствие перекрытия, полное перекрытие и частичное перекрытие.

2. Сначала отсортируйте интервалы

Если это проблема с интервалом, а данные входные данные не отсортированы по порядку, нам может потребоваться рассмотреть возможность сортировки входных данных в неубывающем порядке. первый. В большинстве случаев интервалы представляют собой просто набор периодов времени или целочисленных значений, начинающихся слева направо в 2-мерном пространстве, здесь значения по оси X (красная линия ниже) увеличиваются слева направо. Обратите внимание, что каждый интервал будет иметь значения формата [начало, конец], мы должны сортировать, используя время/значение начала.

Intervals.sort(); //Sort by start time first => Take O(nlogn)

3. Понимание операции слияния

Для неперекрывающихся интервалов нечего объединять. Нам нужно заботиться только о случаях слияния в перекрытии. Сначала нам нужно убедиться, что два интервала перекрываются, прежде чем можно будет выполнить какую-либо операцию слияния. Мы можем сказать, что два интервала перекрываются, если один начинается раньше, чем предыдущий интервал, даже заканчивается.

Check if b.start ≤ a.end for overlapping/mergeable. 
      => mergedIntervalEnd = Math.max(a.end, b.end)

4. Понимание операции пересечения

Для непересекающихся интервалов нет пересечения.

В случае перекрытия лучший способ проверить между A и B – это установить, последний интервал начинается до >самый ранний интервал конец.

Check if Math.max(a.start, b.start) ≤ Math.min(a.end, b.end) 
     =>  intersectInterval = [Math.max(a.start, b.start), Math.min(a.end, b.end)]

Например, в непересекающемся случае, как показано на рисунке ниже, самое позднее начало = Math.max(a.start, b.start) ≥ самое раннее окончание = Math .мин(а.конец, б.конец). В противном случае все остальное будет в перекрывающихся случаях. Поскольку есть перекрытия, будут и пересечения.

5. Практика делает совершенным

Мы можем рассмотреть некоторые типичные проблемы Leetcode, связанные с интервалами слияния/пересечения, чтобы укрепить наше понимание.

Учитывая массив intervals, где intervals[i] = [starti, endi], объединить все перекрывающиеся интервалы и вернуть массив непересекающихся интервалов, которые охватывают все интервалы во входных данных.

Источник: Литкод

С этой проблемой мы можем использовать следующий подход:

  1. В вопросе ничего не упоминается о отсортированном вводе. Основываясь на приеме 2, мы должны сначала отсортироватьна основе времени начала. Этот шаг занимает O(nlogn), что является нижней границей для любого алгоритма сортировки на основе сравнения.
  2. Проверьте, не перекрываются ли какие-либо интервалы, что означает проверку, начинается ли какой-либо интервал до окончания предыдущего. Этот шаг требует просмотра каждого интервала хотя бы один раз, поэтому это занимает O(n) время.
  3. Слияние на основе проверки перекрытия на шаге 2. Вернуть результат. Общее решение занимает O(nlogn) время, а узким местом является сортировка на шаге 1. Примечание: для этого требуется O(n) места. для хранения вывода.

Примечание. Код реализации находится на языке JavaScript, но вы можете легко преобразовать его в язык по вашему выбору.

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

Вам задан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляют начало и конец интервала ith, а intervals отсортировано в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.

Вставьте newInterval в intervals так, чтобы intervals по-прежнему сортировалось в порядке возрастания по starti, а intervals по-прежнему не имело перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

Вернуть intervalsпосле вставки.

Источник: Литкод

С этой проблемой мы можем использовать следующий подход:

  1. Ввод уже отсортирован, поэтому нам не нужно сортировать. Теперь есть шанс, что мы сможем достичь O(n), потому что этап сортировки узких мест удален.
  2. Найдите позицию, которую мы укоротили, вставьте интервал. Мы будем искать первый интервал A[i], у которого конец ≤ начало вставленного интервала. Вставьте сюда новый интервал и оставьте остальные интервалы без изменений. Очевидно, что общая временная сложность составляет O(n), а пространственная сложность — O(n), так как выход будет расти по сравнению с входом.

Мы также можем рассмотреть проблему пересечения.

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов попарно не пересекается и находится в отсортированном порядке.

Возвратите пересечение этих двух списков интервалов.

Замкнутый интервал [a, b] (с a <= b) обозначает набор действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов – это набор действительных чисел, которые либо пусты, либо представлены в виде замкнутого интервала. Например, на пересечении улиц [1, 3] и [2, 4] будет [2, 3].

Источник: Литкод

  1. Опять же, нам не нужно сортировать в этой задаче, потому что входные данные уже отсортированы.
  2. Мы пройдемся по каждому интервалу в первом списке и во втором списке. Мы можем применить трюк 4, как описано выше: если есть перекрытие, есть пересечение, а значит, мы будем проверять на Math.max(a.start, b.start) ≤ Math.min(a.end, b.end ) условий и поместите пересечение в выходной массив.
  3. Общая временная сложность составляет O(M+N) время, где M — длина первого списка, а N — длина второго списка, так как нам нужно увидеть каждый интервал в каждом списке хотя бы один раз. Также требуется O(M+N) пространства для сохранениявыходных данных. Короче говоря, это O(n) как для пространства, так и для времени относительно размера входных данных.

Я надеюсь, что эта статья будет вам полезна, и вы получите удовольствие от решения задач, связанных с интервалами :)