THEORY AND PRACTICE

Input and Output Data

Tasks

Conditions

Tasks

For Loop

Tasks

Strings

Tasks

While Loop

Tasks

Lists

Tasks

Two-Dimensional Arrays

Tasks

Dictionaries

Tasks

Sets

Tasks

Functions and Recursion

Tasks

Lesson 5. While cycle

Difficulty level:

Task«Distribution of rooms in the hotel»

💻 Python

you got a job as an administrator in a small but very popular Cosmos hotel. The previous administrator kept records of guests in a notebook, and confusion constantly arose: the guests were settled in already occupied numbers or, conversely, the rooms were idle, although it would be possible to hand them over. The director set you the task & mdash; To automate the distribution process of guests by numbers.

Your program must accept the list of applications for reservation and determine the room number for each application. The main goal & mdash; Use as few rooms as possible to reduce cleaning and maintenance costs. New rooms should be opened only in case of emergency. If several rooms are released, the guest should be populated into the room with the smallest number.

formal condition:
you have a list of & nbsp; n & nbsp; customers. For each client, the day of his arrival and the day of departure are known. Days are numbered by integer. The guest occupies the number in the morning of the day of arrival and liberates it in the morning of the day of departure. This means that if one guest leaves on the day of X, then the other guest can already call on this room on the same day X.

you need to write a program that for each client (in the order in which they were fed) will determine the room number in which he is in which he will be populated. The numbering of the rooms begins with 1. The algorithm should be “greedy”: always try to populate a new guest in the previously used room with a minimum possible number, and only if there are no free rooms & mdash; Open a new one.

& nbsp;

Input format

& nbsp; n & nbsp; lines. Each line contains two numbers separated by a gap: & nbsp; day_ Recreation & nbsp; and & nbsp; day_nival (integers). These lines submit applications from customers and can be in random order.

at the end there will be a line "end".

Output format

One line containing & nbsp; n & nbsp; numbers separated by a gap. & nbsp; i the number in the line & mdash; This is the room of the room allocated & nbsp; i -the client from the original list.

Example

Input

1 5
8 10
2 4
6 9
1 3

end

Output

1 2 2 1 3

Hint

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

Developer’s solution

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

🎉 Congratulations! 🎉

You did an excellent job with the task! It was a challenging problem, but you found the correct solution. You are one step closer to mastering programming! Keep up the good work, because every stage you pass makes you even stronger.