ТЕОРИЯ И ПРАКТИКА

Ввод и вывод данных

Задачи

Условия

Задачи

Цикл for

Задачи

Строки

Задачи

Цикл while

Задачи

Списки

Задачи

Двумерные массивы

Задачи

Словари

Задачи

Множества

Задачи

Функции и рекурсия

Задачи

Занятие 5. Цикл while

Уровень сложности:

Задача«Распределение номеров в отеле»

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

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

Формальное условие:
Вам дан список из n клиентов. Для каждого клиента известны день его прибытия и день отъезда. Дни нумеруются целыми числами. Гость занимает номер с утра дня прибытия и освобождает его утром дня отъезда. Это значит, что если один гость уезжает в день X, то другой гость уже может заехать в эту комнату в тот же день X.

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

Формат ввода

n строк. Каждая строка содержит два числа, разделенных пробелом: день_прибытия и день_отъезда (целые числа). Эти строки представляют заявки от клиентов и могут быть в произвольном порядке.

В конце будет строка "конец".

Формат Вывода

Одна строка, содержащая n чисел, разделенных пробелом. i-е число в строке — это номер комнаты, выделенный i-му клиенту из первоначального списка.

Пример

Ввод

1 5
8 10
2 4
6 9
1 3

конец

Вывод

1 2 2 1 3

Подсказка

Тут подсказки не будет, решай сам!

main.py

Тест 1

Тест 2

Тест 3

Тест 4

Тест 5

Тест 6

Тест 7

Тест 8

Тест 9

Тест 10

Решение разработчика

# Создаем пустой список для хранения заявок от клиентов
requests = []

# Используем цикл while для считывания всех заявок до слова "конец"
while True:
    # Считываем очередную строку ввода
    line = input()
    
    # Если введена строка "конец", выходим из цикла
    if line == "конец":
        break
    
    # Разделяем строку по пробелу и преобразуем части в целые числа
    arrival_day, departure_day = map(int, line.split())
    
    # Добавляем кортеж с днями прибытия и отъезда в список заявок
    requests.append((arrival_day, departure_day))

# Список для хранения дат отъезда для каждой занятой комнаты.
# Индекс списка - это (номер_комнаты - 1).
# Значение - день, когда комната освободится.
room_departure_dates = []

# Список для хранения результатов - номеров комнат для каждого клиента
assigned_rooms = []

# Инициализируем счетчик для цикла while, чтобы пройти по всем заявкам
request_index = 0

# Основной цикл, который обрабатывает каждую заявку последовательно
while request_index < len(requests):
    # Получаем данные текущего клиента
    current_arrival, current_departure = requests[request_index]
    
    # Флаг, который покажет, нашли ли мы комнату для клиента
    has_found_room = False
    
    # Инициализируем счетчик для поиска свободной комнаты
    room_index = 0
    
    # Вложенный цикл while для поиска подходящей комнаты среди уже существующих
    while room_index < len(room_departure_dates):
        # Комната считается свободной, если новый гость прибывает
        # в тот же день или позже, чем уезжает предыдущий гость.
        if current_arrival >= room_departure_dates[room_index]:
            # Мы нашли подходящую комнату! Обновляем для нее дату отъезда.
            room_departure_dates[room_index] = current_departure
            
            # Добавляем номер комнаты (индекс + 1) в список результатов
            assigned_rooms.append(room_index + 1)
            
            # Устанавливаем флаг, что комната найдена
            has_found_room = True
            
            # Прерываем поиск, так как мы должны выбрать комнату с наименьшим номером
            break
            
        # Переходим к проверке следующей комнаты
        room_index += 1
    
    # Если после проверки всех комнат свободная так и не нашлась
    if not has_found_room:
        # "Открываем" новую комнату, добавляя дату отъезда нового гостя в конец списка
        room_departure_dates.append(current_departure)
        
        # Номер новой комнаты будет равен текущему количеству комнат
        new_room_number = len(room_departure_dates)
        
        # Добавляем номер новой комнаты в список результатов
        assigned_rooms.append(new_room_number)
        
    # Переходим к обработке следующей заявки
    request_index += 1

# Выводим все назначенные номера комнат в одну строку через пробел
print(*assigned_rooms)

🎉 Поздравляем! 🎉

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