2

В отеле имеется k одинаковых номеров. На ближайший сезон длины l имеется n бронирований. Каждое бронирование содержит начало и конец. Необходимо разработать алгоритм, который за время O(n*logn) определит, возможно ли удовлетворить все бронирования.

Я создаю 3 массива:

int arr[l]; // заполняем нулями
int a[n], b[n]; // a - начало i-го бронирования, b - конец

Потом использую двойной цикл. Рассматриваются i-ые элементы массивов a и b, во внутреннем цикле рассматривается массив arr в промежутке от a[i] до b[i], каждый элемент массива arr увеличивается на 1 - это значит, что в день j занято arr[j] номеров отеля. Если arr[j] окажется больше k, то становится понятно, что удовлетворить все заявки невозможно, циклы останавливаются.

for (int i = 0; i < n; i++)
{
    for (int j = a[i]; j <= b[i]; j++)
    {
        arr[j]++;
        if (arr[j] > k)
        {
            err = 1;
            break;
        }
    }
}

Если рассмотреть такую ситуацию, что имеется n бронирований длиной n, причем в отеле есть хотя бы n номеров, то получится, что мы обработаем все брони, получим удовлетворительный ответ. Но работа алгоритма займет время O(n*n) (n раз совершить n увеличений на 1). Как улучшить время?

Воспроизводимый код:

#include <iostream>
#include <time.h>

using namespace std;

int main()
{
    srand(time(NULL));

    int err = 0;

    const int n = 6;
    const int l = n;
    const int k = n;

    int arr[l];
    for (int i = 0; i < l; i++)
    {
        arr[i] = 0;
    }

    int a[n], b[n];
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % (l - 1);
        b[i] = a[i] + rand() % ((l - 1) - a[i]) + 1;
        cout << a[i] << " - " << b[i] << endl;
    }
    cout << endl;

    for (int i = 0; i < n; i++)
    {
        for (int j = a[i]; j <= b[i]; j++)
        {
            arr[j]++;
            if (arr[j] > k)
            {
                err = 1;
                break;
            }
        }
    }
}

1 ответ 1

3

Сразу можно заметить, что условие недостаточно четко поставлено. Не оговорен важный момент: если один постоялец убывает в тот же день, когда прибывает другой, то могут ли они быть поселены в одну комнату? Также, аналогично: возможно ли во входных данных прибытие и убытие постояльца в один и тот же день? И если возможно, то занимает ли такой постоялец комнату?

Трудоемкость грамотного решения такой задачи не должна зависеть от длин вовлечённых интервалов.

Отсортируйте все точки прибытия-убытия в одну последовательность (сохранив при этом возможность отличать прибытия от убытий). Затем просто пройдитесь по ним по порядку, фактически симулируя ход времени. Когда "прибывает" новый постоялец, счётчик активных отрезков увеличивается на 1, когда "убывает" - счётчик уменьшается на 1. Максимальное значение счётчика, достигнутое за полный проход, даст вам ответ на вопрос о том, можно ли разместить всех гостей.

Как правильно заметил @pavel в комментариях, имеет смысл располагать прибытия перед убытиями для каждого момента времени. Альтернативно, можно не вводить такого дополнительного упорядочения, но оценивать значение счётчика только после того, как все прибытия-убытия для данного момента времени уже обработаны. В любом варианте, детали могут/будут зависеть от вышеупомянутых уточнений условия.

P.S. Более интересной была бы задача о минимальном количестве комнат, необходимом для удовлетворения всех бронирований. А ответ на вопрос "можно или нельзя" получается вот так достаточно тривиально.

5
  • 2
    2 замечания. 1 - отрезок надо делить на 2 точки и сортировать именно точки. 2 - закрывающая точка при одинаковых координатах должна быть раньше.
    – pavel
    27 ноя 2019 в 21:03
  • Создал вектор пар vector<pair<int, string>> reservations с отметками in или out, отсортировал встроенным алгоритмом sort(). так и не сообразил компаратор, который ставил бы сначала out, а потом in, поэтому, я так понимаю, временная сложность увеличивается на константу (чем если бы сначала шли out), так как становится больше сравнений, чтобы не выйти за пределы вектора и знать, что все события текущего дня обработаны, - if (i + 1 < reservations.size() && reservations[i + 1].first != reservations[i].first && reserved_rooms > k) 28 ноя 2019 в 9:19
  • а, можно же банально писать aout и bin, тогда закрывающие будут идти первее. :) 28 ноя 2019 в 11:25
  • @Halva: С одной стороны, вы беспокоитесь о какой-то исчезающе малой компоненте временной сложности, а с другой, вы используете строки (!) для пометки прибывающих/убывающих??? 28 ноя 2019 в 15:14
  • @AnT, конечно, беспокоюсь не для себя, а для формального результата, чтобы сдать задание. Но вас понял, да, мог бы и без строк обойтись. 28 ноя 2019 в 19:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.