|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
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 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Хорошая книжка: С. Скиена, "Алгоритмы: руководство по разработке".
Первое правило алгориста: не знаете, что делать с данными - попробуйте отсортировать. В данном случае копируем массив заказов, сортируем первый по прибытию, второй по убытию, идём курсорами по обоим. |
12.01.2013, 01:29 | #3 |
МегаМодератор
СуперМодератор
Регистрация: 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. |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Перегрузка 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 |