Заимствуйте сортировку пациентов: порядок в очереди задач
Почему это важно "Используйте очередь с приоритетами" - рефлекс для любой очереди с приоритетами. Он отвечает на "кто важнее всех?", когда настоящий вопрос часто "кто меньше всех может ждать?". Другие области отвечают на этот вопрос давно.
Три стойки
Приёмное отделение больницы. Медсестра сортировки относит каждого прибывшего к категории, и у каждой категории есть целевое время осмотра: в широко используемой Манчестерской системе - немедленно, в течение 10 минут, 60, 120 или 240. Когда врач освобождается, следующим идёт не просто самый тяжёлый пациент в зале: обычный пациент, который вот-вот выйдет за своё целевое время, может пройти раньше срочного, прибывшего минуту назад, у которого ещё есть время.
Регистрация в аэропорту. Есть отдельные очереди для премиума и эконома. Внутри очереди людей обслуживают в порядке прибытия. Но когда регистрация на рейс вот-вот закроется, сотрудники идут вдоль очереди эконома и вызывают пассажиров этого рейса вперёд, раньше премиальных пассажиров, чьи рейсы вылетают позже.
Стойка возврата книг в библиотеке. Одна очередь, обслуживаемая строго по порядку. Никого никогда не обгоняют, и ничья срочность не учитывается.
Сравните, прежде чем писать код
- Что на каждой стойке решает, кого обслужат следующим?
- На каких стойках кто-то может ждать вечно? На каких срочный случай может ждать слишком долго?
- Больница и аэропорт совсем не похожи. Что у них общего? Запишите это одним предложением, где нет ни больниц, ни самолётов.
- Почему в аэропорту достаточно смотреть на начало каждой очереди?
Цель
Система фоновых задач работает на одном обработчике, который тратит ровно одну минуту на задачу. Задачи бывают интерактивными (приоритет 1), стандартными (2) или пакетными (3), и у каждого приоритета есть обещание обслуживания: дольше всего, сколько задача этого приоритета может ждать до старта. Текущий планировщик всегда запускает ожидающую задачу с наивысшим приоритетом, и пакетные задачи каждый день после обеда нарушают своё обещание.
Напишите order(jobs, max_wait). jobs - список {"id", "arrive", "priority"}, отсортированный по arrive (целые минуты); max_wait сопоставляет приоритет с наибольшим числом минут, которое задача может ждать. Верните id задач в порядке, в котором их запускает обработчик. Обработчик запускает одну задачу в минуту: задача стартует в более позднее из двух - время её прибытия и окончание предыдущей задачи, а её ожидание - старт минус прибытие. Правило: ни одна задача не может ждать дольше max_wait[priority]. Все тестовые дни можно обслужить без опозданий; при {1: 3, 2: 20, 3: 60} в дне около 1 000 задач.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.