В продолжение нашего приключения Blind 75, сегодня мы займемся разделом Interval.

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

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

Базовая стратегия

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

{ start: 2, end: 5 } // object node
[2, 5] // array of 2 elements node

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

  1. отсортировать узлы по времени начала
  2. рассмотрите каждую пару интервалов, как правило, будет использоваться приведенная ниже утилита (обратите внимание, что перекрытие иногда может быть curr[1] > next[0] или curr[1] >= next[0])
const isOverlap = (curr, next) => curr[1] > next[0]

Мы рассмотрим каждую проблему и лучше поймем 2 пункта выше

57. Вставить интервал

var insert = function(intervals, newInterval) {
  let lng = intervals.length
  const res = []
    
  let i = 0;
  
  while (i < lng) {
    if (isOverlap(intervals[i], newInterval)) break;
    res.push(intervals[i])
    i++
  }
  
  while (i < lng) {
    if (!isOverlap(newInterval, intervals[i])) break
    newInterval[0] = Math.min(newInterval[0], intervals[i][0])
    newInterval[1] = Math.max(newInterval[1], intervals[i][1])
    i++
  }
  
  res.push(newInterval)
  
  while (i < lng) {
    res.push(intervals[i++])
  }
  
  return res
};
const isOverlap = (curr, next) => curr[1] >= next[0]

intervals отсортировано в порядке возрастания по start

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

У нас есть 3 разных цикла while. Где мы останавливаемся и начинаем каждый цикл, определяется нашей утилитой isOverlap для сравнения каждой пары интервалов.

  1. Первый — найти первую точку, в которой происходит перекрытие.
  2. Во-вторых, объединить intervals с newInterval
  3. Последний похож на первый, просто собираем все, что осталось. также можно записать как
if (i < lng) {
  res.push(...intervals.slice(i))
}

56. Объединить интервалы

var merge = function(intervals) {
  const lng = intervals.length;
  const res = [];
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < lng; i++) {
    const curr = intervals[i];
    const next = intervals[i + 1];
    if (next && overlap(curr, next)) {
      let j = i + 1;
      while (j < lng) {
        const tnext = intervals[j];
        if (!overlap(curr, tnext)) break;
        curr[0] = Math.min(curr[0], tnext[0]);
        curr[1] = Math.max(curr[1], tnext[1]);
        j++;
      }
      i = j - 1;
    }
    res.push(curr);
  }
  
  return res;
};
const overlap = (a, b) => {
  return a[1] >= b[0];
}

Хотя это решение кажется отличным от Вставить интервал, они очень похожи по своей сути. Самая большая разница заключается в том, что если в первой задаче есть только один объединенный блок, то в этой задаче может быть несколько блоков, которые можно объединить. Из-за этого нам нужно переместить наш цикл слияния while внутрь большего цикла for.

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

intervals.sort((a, b) => a[0] - b[0])

Всякий раз, когда мы находим пару столкнувшихся интервалов, мы начинаем их объединять и использовать указатель j для отслеживания всех объединенных блоков. После того, как мы закончим слияние, мы установим наш текущий указатель i туда, где находится j, и продолжим как обычно.

435. Непересекающиеся интервалы

var eraseOverlapIntervals = function(intervals) {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[0] - b[0]);
  const dp = new Array(intervals.length).fill(1);
  for (let i = 1; i < intervals.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (!isOverlap(intervals[j], intervals[i])) {
        dp[i] = Math.max(dp[j] + 1, dp[i - 1]);
        break;
      }
    }
  }
  const max = Math.max.apply(Math, dp);
  return intervals.length - max;
};
const isOverlap = (a, b) => a[1] > b[0];

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

  1. Blind 75 Javascript Edition — динамическое программирование (часть 1)
  2. Blind 75 Javascript Edition — динамическое программирование (часть 2)

Однако некоторые основы решения проблем с интервалами все же можно применить и здесь. Как обычно, нам нужно сортировать входные данные и использовать нашу функцию isOverlap util. Идея здесь в том, что для любого заданного индекса мы будем выполнять итерацию в обратном направлении, чтобы найти точку перекрытия. Нам нужно будет решить, будем ли мы сохранять текущий интервал (по индексу i) или предыдущий интервал (по индексу j) — это концепция рюкзак 0/1. Значение dp для каждого индекса — это максимальное количество интервалов, которые могут быть включены до этого индекса. Когда наступит условие if (!isOverlap(intervals[j], intervals[i])), мы перейдем к 1 из 2 результатов, указанных ниже.

  1. Если мы берем текущий интервал с индексом i, нам нужно удалить все интервалы между i and j, поскольку они пересекаются с интервалом с индексом i. Значение dp[j] будет иметь максимальное количество до индекса j и плюс 1, чтобы получить наш текущий результат (dp[j] + 1)
  2. Если мы пропустим текущий интервал с индексом i, мы будем использовать значение dp[i — 1], чтобы получить максимум до индекса непосредственно перед i

Какой выбор сделать, зависит от результата Math.max между этими двумя значениями. При дальнейшем расширении этого решения мы сможем построить массив dp, состоящий из всех максимальных непересекающихся интервалов, вплоть до этого конкретного индекса. Нам просто нужно вычислить максимальное значение из этого массива, а затем вычесть из общего числа интервалов (intervals.length), чтобы получить окончательный результат.

252. Конференц-залы

var canAttendMeetings = function(intervals) {
  intervals.sort((a, b) => a[0] - b[0])
  
  for (let i = 0; i < intervals.length - 1; i++) {
    const curr = intervals[i]
    const next = intervals[i + 1]
    if (isOverlap(curr, next)) return false
  }
  
  return true
};
const isOverlap = (curr, next) => curr[1] > next[0]

Это довольно простая проблема. Используя то, что мы знаем до сих пор

  1. сначала нам нужно отсортировать интервалы, так как условие задачи не дает нам отсортированных входных данных
  2. Мы запускаем наш intervals через наш isOverlap util. Всякий раз, когда мы обнаруживаем коллизию, мы знаем, что не можем присутствовать на всех собраниях, поэтому в результате возвращаем false

253. Конференц-залы II

var minMeetingRooms = function(intervals) {
  const start = []
  const end = []
  
  for (let [s, e] of intervals) {
    start.push(s)
    end.push(e)
  }
  
  start.sort((a, b) => a - b)
  end.sort((a, b) => a - b)
  
  let res = 0;
  let e = 0;
  for (let s = 0; s < start.length; s++) {
    if (start[s] < end[e]) res++
    else e++
  }
  
  return res
};

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

[0, 10], [2, 3], [4, 6]

Наш первый [0, 10] блок будет причиной того, что нам понадобится две комнаты, чтобы уместить все расписание. Из-за этого сравнение [0, 10] только с одной другой парой будет недостаточным. Нам нужно извлечь все начальное и конечноевремя, а также увеличивать количество комнат всякий раз, когда время начала раньше, чем время окончания (если собрание должно начаться до окончания другого, мы не можем использовать ту же комнату).

Заключение

Подобно этим складывающимся блокам Lego, интервалы — это просто блоки времени, складывающиеся вместе. Хотя перед кодированием всегда рекомендуется рисовать решения, это особеннорекомендуется при выполнении интервальных задач. Эти проблемы, как правило, довольно просты, и решения можно легко увидеть, когда блоки вытянуты, чтобы определить пересекающиеся отношения.