Question

На вход программе подаются сведения о пассажирах, желающих сдать багаж в камеру хранения до полуночи. В первой строке указано число пассажиров N (от 3 до 1000), во второй — количество ячеек M (от 10 до 1000). Каждая из следующих N строк содержит:

<Фамилия> <время_сдачи> <время_освобождения>

где <Фамилия> — строка из непробельных символов (не более 20); <время_сдачи> и <время_освобождения> — время в формате ЧЧ:МММ (часы от 00 до 23, минуты от 00 до 59). Время освобождения больше времени сдачи. Данные отсортированы по времени сдачи.

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

Требуется вывести для каждого пассажира, получившего ячейку, его фамилию и номер ячейки.

Пример входных данных:

3
10
Иванов 09:45 12:00
Петров 10:00 11:00
Сидоров 12:00 13:12

Ожидаемый вывод:

Иванов 1
Петров 2
Сидоров 1

Accepted Answer

Иванов 1
Петров 2
Сидоров 1

Answer

Идея решения: для каждой ячейки хранить время окончания текущего хранения; при поступлении нового пассажира найти первую ячейку, которая свободна (время окончания ≤ текущему времени сдачи), и выделить её.

Алгоритм:
1. Инициализировать массив времён окончания для всех ячеек нулями (ячейки свободны).
2. Для каждого пассажира прочитать фамилию и оба времени, переведя их в минуты от начала суток.
3. Последовательно проверить ячейки с номера 1 до M: если ячейка свободна (время окончания ≤ времени сдачи), выделить её, обновить время окончания и вывести фамилию с номером ячейки.
4. Если подходящей ячейки не найдено, пассажир не получает ячейку.

**Решение на Паскале:**

```pascal
var
  p: array[1..1000] of integer;
  c, c1: char;
  i, j, N, K: integer;
  name: string;
  time1, time2: integer;
begin
  readln(N, K);
  for i := 1 to K do
    p[i] := 0;
  for i := 1 to N do
  begin
    name := '';
    repeat
      read(c);
      name := name + c
    until c = ' ';
    read(c, c1);
    time1 := 60 * ((ord(c) - ord('0')) * 10 +
                    ord(c1) - ord('0'));
    read(c, c, c1);
    time1 := time1 + (ord(c) - ord('0')) * 10 +
                     ord(c1) - ord('0');
    read(c, c, c1);
    time2 := 60 * ((ord(c) - ord('0')) * 10 +
                    ord(c1) - ord('0'));
    readln(c, c, c1);
    time2 := time2 + (ord(c) - ord('0')) * 10 +
                     ord(c1) - ord('0');
    for j := 1 to K do
      if p[j] <= time1 then
      begin
        p[j] := time2;
        writeln(name, ' ', j);
        break;
      end;
  end;
end.
```

**Решение на Python:**

```python
n, k = map(int, input().split())
p = [0] * (k + 1)

for _ in range(n):
    line = input().split()
    name = line[0]
    time1_str = line[1]
    time2_str = line[2]
    
    h1, m1 = map(int, time1_str.split(':'))
    time1 = h1 * 60 + m1
    
    h2, m2 = map(int, time2_str.split(':'))
    time2 = h2 * 60 + m2
    
    for j in range(1, k + 1):
        if p[j] <= time1:
            p[j] = time2
            print(name, j)
            break
```

Задание №19Алгоритмы и исполнителиЕГЭ по информатике