UniLecs #Task. Барбершоп
Задача: в барбершопе работает один мастер. Он тратит на одного клиента ровно 20 минут, а затем сразу переходит к следующему, если в очереди кто-то есть. Если в очереди никого, то ждет след.клиента.
В течение дня есть данные о времени прихода клиентов в барбершоп. Также заранее известна степень терпения каждого клиента. Степень показывает, сколько человек может максимально находиться в очереди перед клиентом, чтобы он дождался своей очереди и не ушел раньше. Т.е. если в момент прихода клиента в очереди находится больше людей, чем степень его терпения, то он уходит. Клиент, который уже обслуживается в данный момент, также считается находящимся в очереди.
Необходимо для каждого клиента вывести время его выхода из барбершопа.
Входные данные: clients (h, m, d) — список с данными клиента, где
(h, m, d) — h — часы от 0 до 23, m — минуты от 0 до 59, d — степень терпения клиента (неотрицательное число не более 100).
Вывод: вывести время (часы и минуты) выхода каждого клиента из барбершопа.
Примечание: если на момент прихода клиента человек в очереди больше, чем степень его терпения, то можно считать, что время его ухода равно времени прихода. Барбершоп работает круглосуточно :)
Пример:
1. [ (10, 0, 0), (10, 1, 1), (10, 2, 1) ];
Output:
10:20
10:40
10:02
2. [ (1, 0, 100), (2, 0, 0), (2, 1, 0), (2, 2, 3), (2, 3, 0) ];
Output:
1:20
2:20
2:01
2:40
2:03
Разбор
Смоделируем очередь клиентов. Заведем массив, в котором будем хранить ответ для каждого клиента (время его ухода) и очередь, в которой будем хранить времена ухода клиентов, которые в настоящий момент находятся в парикмахерской.
Все времена удобно хранить в виде числа минут, прошедших от начала суток (т. е. время в h часов и m минут удобно хранить, как 60 * h + m).
Как происходит обработка очередного клиента:
- Прежде всего, выкинем из очереди всех, кто уйдет до прихода этого клиента.
- Затем проверим оставшееся число клиентов в очереди. Если оно больше уровня недовольства нового клиента — то мы не добавляем этого клиента в очередь, сразу же определяем для него ответ (это время его прихода) и переходим к следующему клиенту. Иначе определяем время ухода этого клиента из парикмахерской. Если в парикмахерской никого нет — то это время его прихода плюс 20 минут, а если кто-то есть — то это время ухода последнего клиента из очереди плюс 20 минут. После чего нового клиента добавляем в очередь.
Реализация
https://gist.github.com/unilecs/5d5876d1a0b9f1dd51502f3d11b78c7f
