Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.01.2013, 00:48   #1
Люля.
 
Регистрация: 09.06.2010
Сообщений: 4
Лампочка Сложность O(n*log n)

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

Пожалуйста, натолкните хоть на мысль КАК это делать. С пониманием сложности работы алгоритма огромные проблемы (
Люля. вне форума Ответить с цитированием
Старый 12.01.2013, 01:26   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Хорошая книжка: С. Скиена, "Алгоритмы: руководство по разработке".
Первое правило алгориста: не знаете, что делать с данными - попробуйте отсортировать. В данном случае копируем массив заказов, сортируем первый по прибытию, второй по убытию, идём курсорами по обоим.
Abstraction вне форума Ответить с цитированием
Старый 12.01.2013, 01:29   #3
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Пока в голову приходит только алгоритм O(n*k).
Создаем массив на k дат отбытия - номера гостиницы.
Заполняем заведомо меньшими датами, чем будут поданы на вход.
Берем переменную i и приравниваем 0 (указывает на 1 номер).
В цикле от 1 до n:
Считываем дату прибытия.
Проверяем, что можно заселить в i номер - если можно, то считываем дату отбытия и заносим в массив.
Если нельзя, то начинаем проверять для i+1, i+2,..., k-1, 0, 1,..., i-1 номеров.
Если нашли такой номер, то заносим туда время отбытия, иначе обрабатываемый заказ нельзя исполнить - выходим из цикла с соответствующим сообщением.
Если цикл прошел до конца, то мы смогли выполнить все заказы.

Да, алгоритм предполагает, что заказы поступают отсортированными по времени прибытия.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 12.01.2013 в 01:51.
BDA на форуме Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перегрузка Log(2) Prin53 Общие вопросы C/C++ 9 16.03.2012 19:15
LOG скачиваемых файлов kzld Софт 0 06.01.2012 08:26
E2015 Ambiguity between 'std::log(double)' and 'std::log(long double)' Namolem Помощь студентам 3 02.04.2011 20:22
f=-log(по осн 2)|x^2/(y-1)| Vlad2104 Помощь студентам 0 27.05.2010 21:08
.log файлы TyoshA Общие вопросы Delphi 12 25.03.2008 08:31