Перевод статьи подготовлен специально для студентов курса «Алгоритмы для разработчиков».



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

---

Задача

• Задача: InterviewBit

Менеджер отеля должен обработать N заказов на бронирование номеров на следующий сезон. В его отеле есть K номеров. Информация о бронировании содержит дату заезда и дату выезда. Менеджер хочет выяснить, достаточно ли номеров в отеле, чтобы удовлетворить спрос.

Входные данные:

— Первым на вход подается список с информацией о времени заезда
— Вторым — список с информацией о времени выезда
— Третьим — К, обозначающее количество номеров

Выходные данные:
— Логическое значение, которое обозначает возможность забронировать номера
false означает, что в отеле не достаточно номеров для N бронирований
true означает, что в отеле достаточно номеров для N бронирований

Пример:

Входные данные:
— заезд = [1, 3, 5]
— выезд = [2, 6, 10]
— К = 1

Выходные данные: false. В день = 5 в отеле 2 гостя. Но у нас есть только один номер.

• Категория: Массивы

Процесс решения

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

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

Входные данные:
— въезды = [1, 3, 5]
— выезды = [2, 6, 10]
— k = 1

Для этого примера размер массива будет равен 10 (потому что последний выезд в день 10). Чтобы заполнить этот массив, мы проходимся по спискам въездов и выездов и увеличиваем или уменьшаем счетчик соответствующего дня. Пример на псевдокоде:

int[] counts = new int[maxDepartures(departures)]
for each arr in arrivals {
 counts[arr]++
}
for each dep in departures {
 counts[dep]--
}

В итоге мы получим следующий массив:

значение: 1 0 1 1 2 1 1 1 1 0
индекс: 1 2 3 4 5 6 7 8 9 10

После того, как массив заполнен, нужно просто пройтись по нему и проверить, все ли элементы не превышают k (количество комнат).

В предыдущем примере максимальное количество номеров было 1. Поскольку в день 5 у нас есть 2 бронирования, мы возвращаем false.

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

Например:

Входные данные:
— въезды = [1, 3, 5]
— выезды = [2, 10000, 10]
— k = 1

В данном случае будет выделен массив из 10 тысяч целых чисел.

Давайте посмотрим на другие варианты решения.

Хранение коллекции событий

Какие есть другие варианты? Давайте еще раз посмотрим, что у нас получалось с предыдущей структурой:

значение: 1 0 1 1 2 1 1 1 1 0
индекс: 1 2 3 4 5 6 7 8 9 10

Мы видим, что некоторая информация дублируется. Например, между 6 и 9 днями количество бронирований не меняется, так как мы знаем, что за этот период времени ничего не произойдет.

Может станет лучше, если вместо этого хранить события? Давайте снова возьмем тот же пример:

Входные данные:
— въезды = [1, 3, 5]
— выезды = [2, 6, 10]
День 1: +1 бронирование
День 2: -1 бронирование
День 3: +1 бронирование
День 6: -1 бронирование
День 5: +1 бронирование
День 10: -1 бронирование

Решение заключается в том, чтобы, перебирая эти события, увеличивать или уменьшать счетчик. Если в какой-то момент счетчик больше k, мы возвращаем false. Однако, чтобы выполнить перебор, эту коллекцию событий нужно отсортировать.

Какую структуру здесь лучше использовать? Давайте обобщим наши требования:

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

Как насчет использования двоичного дерева поиска (Binary Search Tree, BST)?

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

class Node {
 int day
 int count
 Node left
 Node right
}

Сортировка будет производиться по полю day.

Давайте посмотрим на последствия с точки зрения временной сложности:

• Поиск, чтобы проверять, существует ли уже такой день: O(log(n)) в среднем случае, O(n) в худшем случае,
• Добавление нового дня: O(log(n)) в среднем случае, O(n) в худшем случае,
• Просмотр структуры для перебора каждого отсортированного дня: O(n), используя поиск в глубину.

Поскольку нам приходится перебирать каждый элемент и вставлять его в дерево, сложность алгоритма составляет O(n log(n)) в среднем случае, O(n?) в худшем случае.

Другой вариант — использование хеш-таблицы и сортировка ключей после добавления всех событий:

• Поиск, чтобы проверять, существует ли уже такой день: O(1) в среднем случае, O(n) в худшем случае (вероятность зависит от емкости ассоциативного массива),
• Добавление нового дня: O(1) в среднем случае, O(n) в худшем случае,
• Просмотр структуры для перебора каждого отсортированного дня: O(n log(n)) для сортировки ключей и O(n) для перебора.

В конце концов, решение имеет O(n log(n)) в среднем случае (из-за операции сортировки), O(n?) в худшем случае. Похоже, это решение имеет ту же сложность, что и решение, использующее дерево.

Давайте посмотрим на возможную реализацию на Java, используя отсортированный ассоциативный массив:

public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) {
  // Коллекция событий
  Map<Integer, Integer> events = new HashMap<>();

  // Количество номеров
  int n = arrivals.size();

  for (int i = 0; i < n; i++) {
    int arrival = arrivals.get(i);
    int departure = departures.get(i);

    // Прибавляем один для каждого въезда
    Integer current = events.get(arrival);
    events.put(arrival, current == null ? 1 : current + 1);

    // Отнимаем один для каждого выезда
    current = events.get(departure);
    events.put(departure, current == null ? -1 : current - 1);
  }

  // Сортируем ассоциативный массив
  Map<Integer, Integer> sortedEvents = new TreeMap<>(events);

  int count = 0;
  for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) {
    count += entry.getValue();

    // Если count превышает максимальное количество номеров
    if (count > k) {
      return false;
    }
  }

  return true;
}

Постоянная пространственная сложность

Если мы хотим оптимизировать наш алгоритм, нам нужно подумать, действительно ли необходимо хранить все эти события? Разве мы не можем просто перебирать данные коллекции (въезды и выезды) и проверять ограничение на бронирования в процессе?

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

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

Как вы можете видеть, во время каждой итерации нам все еще нужно проверять минимум между arrivals.get(indexArrival) и departures.get(indexDeparture), чтобы узнать, какой указатель нужно обновить.

В целом, алгоритм имеет постоянную временную и пространственную сложность O(n log(n)) из-за операций сортировки.