THEORIE UND PRAXIS

Eingabe und Ausgabe

Aufgaben

Bedingungen

Aufgaben

For-Schleife

Aufgaben

Zeichenketten

Aufgaben

While-Schleife

Aufgaben

Listen

Aufgaben

2D-Arrays

Aufgaben

Wörterbücher

Aufgaben

Mengen

Aufgaben

Funktionen und Rekursion

Aufgaben

Lektion 5. While cycle

Schwierigkeit:

Aufgabe«Hotelzimmer verteilen»

💻 Python

Sie haben einen Job als Administrator in einem kleinen, aber sehr beliebten Hotel Cosmos bekommen. Der vorherige Administrator führte Aufzeichnungen über Gäste in einem Notizbuch, und es kam ständig zu Verwirrung: Die Gäste wurden in bereits belegte Zimmer eingewiesen oder umgekehrt standen Zimmer leer, obwohl sie hätten vergeben werden können. Der Direktor hat Ihnen die Aufgabe gestellt — den Prozess der Zimmerverteilung an Gäste zu automatisieren.

Ihr Programm muss die Liste der Reservierungsanträge entgegennehmen und für jeden Antrag die Zimmernummer bestimmen. Das Hauptziel — so wenige Zimmer wie möglich zu nutzen, um Reinigungs- und Wartungskosten zu senken. Neue Zimmer sollten nur im Notfall geöffnet werden. Wenn mehrere Zimmer frei werden, soll der Gast in das Zimmer mit der kleinsten Nummer einziehen.

Formale Bedingung:
Sie haben eine Liste von n Kunden. Für jeden Kunden sind der Anreisetag und der Abreisetag bekannt. Die Tage werden durch ganze Zahlen nummeriert. Der Gast belegt das Zimmer am Morgen des Anreisetages und gibt es am Morgen des Abreisetages frei. Das bedeutet, dass wenn ein Gast am Tag X abreist, ein anderer Gast am selben Tag X bereits in dieses Zimmer einziehen kann.

Sie müssen ein Programm schreiben, das für jeden Kunden (in der Reihenfolge, in der sie eingegeben wurden) die Zimmernummer bestimmt, in das er einziehen wird. Die Nummerierung der Zimmer beginnt mit 1. Der Algorithmus soll "gierig" sein: Versuchen Sie immer, einen neuen Gast in ein zuvor genutztes Zimmer mit der kleinstmöglichen Nummer einzuweisen, und nur wenn keine freien Zimmer vorhanden sind — öffnen Sie ein neues.

Eingabeformat

n Zeilen. Jede Zeile enthält zwei durch ein Leerzeichen getrennte Zahlen: day_arrival und day_departure (ganze Zahlen). Diese Zeilen übermitteln Anfragen von Kunden und können in beliebiger Reihenfolge sein.

Am Ende folgt eine Zeile mit "end".

Ausgabeformat

Eine Zeile mit n Zahlen, getrennt durch ein Leerzeichen. i die Zahl in der Zeile — Dies ist die Nummer des Raums, der i -ten Kunden aus der ursprünglichen Liste zugewiesen wurde.

Beispiel

Eingabe

1 5
8 10
2 4
6 9
1 3

Ende

Ausgabe

1 2 2 1 3

Hinweis

There will be no clue here, decide for yourself!

main.py

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Entwicklerlösung

# Создаем пустой список для хранения заявок от клиентов
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)