Question

Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения.Задание 26

В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты.Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки. **Входные данные.**В первой строке входного файла находится натуральное число *K*, не превышающее 1000, — количество ячеек в камере хранения.Во второй строке — натуральное число *N* (*N* ≤ 1000), обозначающее количество пассажиров. Каждая из следующих *N* строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и номер последней занятой ячейки.**Типовой пример организации данных во входном файле:**2530 6040 100059 6061 10001010 1440При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры.Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны.*Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.*

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

В первой строке входного файла находится натуральное число $K$ (не превышает 1000) — количество ячеек в камере хранения. Во второй строке — натуральное число $N$ ($N \leq 1000$), обозначающее количество пассажиров. Каждая из следующих $N$ строк содержит два натуральных числа, каждое не превышает 1440: время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).

Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит.

Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.

**Пример входных данных:**
```
2
5
30 60
40 100
59 60
61 100
10 1440
```

При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны.

### РЕШЕНИЕ

Идея решения: отсортировать заявки по времени прихода, затем для каждого пассажира найти ячейку с минимальным номером, которая освободилась не позже времени его прихода.

Для каждой ячейки будем отслеживать время её освобождения. Изначально все ячейки свободны (время освобождения = 0). Заявки сортируем по времени прихода. Для каждого пассажира ищем среди всех ячеек ту, у которой время освобождения меньше времени прихода пассажира. Если такая ячейка найдётся, пассажир обслуживается, ячейка занимается до времени его ухода, и мы запоминаем номер этой ячейки. Если свободных ячеек нет, пассажир уходит.

```python
f = open('1_26.txt')
K = int(f.readline())
N = int(f.readline())

passengers = []
for _ in range(N):
    arrival, departure = map(int, f.readline().split())
    passengers.append((arrival, departure))

passengers.sort()

lockers = [0] * K
served = 0
last_locker = 0

for arrival, departure in passengers:
    free_lockers = [i for i in range(K) 
                    if lockers[i] < arrival]
    if free_lockers:
        locker_idx = min(free_lockers)
        lockers[locker_idx] = departure
        served += 1
        last_locker = locker_idx + 1

print(served, last_locker)
```

Сложность: $O(n \log n + n \cdot k)$, где $n$ — количество пассажиров, $k$ — количество ячеек. Сортировка требует $O(n \log n)$, для каждого пассажира ищем свободную ячейку за $O(k)$.

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике