Описание задачи
Нужно перевезти группу из N человек со станции A на станцию B (прямые рейсы), используя один или несколько поездов.
Логика выбора поездов
- Рассматриваем поезда, отправляющиеся после заданного времени.
- Набрать поезда так, чтобы суммарная вместимость была ≥ N.
- Приоритет: уехать как можно раньше (по времени отправления последнего необходимого поезда).
- Если время одинаковое — выбирать тот, где больше мест.
Формат входных данных
> Timetable:
+ Отпр Приб Вместимость Компания
...
> Query:
? Время_начала Кол-во_людей
Пример
Расписание
+ 08:00:00 09:30:00 10 RegioJet
+ 06:45:00 08:15:00 100 Arriva
+ 09:20:00 10:50:00 35 Ceske_drahy
Query: ? 1:01:01 120
1: 6:45:00 8:15:00 100 Arriva
3: 9:20:00 10:50:00 20 Ceske_drahy
Нужно 120 мест. Берём рейс №1 (100 мест). Осталось 20. Рейс №3 подходит (35 мест, берём 20). Рейс №2 (08:00) пропущен, так как №3 (09:20) в комбинации с №1 даёт нужную вместимость, но условие "уехать как можно раньше" относится к времени отправления последнего поезда в группе? Нет, обычно минимизируется время, когда вся группа сможет выехать. Здесь логика может быть жадной или переборной.