Уровень: easy
Еще одна задача на очереди со следующим условием: в очереди стоят люди за билетами. Каждому человеку нужно купить Х билетов. За один подход к кассе человек может купить только 1 билет и встать в конец очереди, если ему нужны еще билеты. Покупка одного билета одним человеком занимает 1 секунду. Нужно посчитать, сколько секунд займет покупка всех билетов человеком, который стоит на k-ой позиции в очереди.
Например, в очереди стоят люди, которым нужно купить [1, 3, 2, 2] билетов соответственно. Нужно посчитать кол-во секунд, которое займет покупка всех билетов у человека, находящегося на 3-ей позиции (1-ый человек находятся на позиции 0).
После первого круга:
[0,2,1,1] - 4 секунды
После второго круга:
[1,0,0] - 3 секунды (наш человек купил билет)
Итого: 7 секунд
Важно: когда показатель стал 0 (т.е. человек больше не нуждается в билетах), он покидает очередь.
Можно решить с использованием очередей (задача же на очереди, хех), но там будет пространственная сложность O(n), так как мы будем хранить в очереди людей из массива (точнее, нужно им кол-во билетов), и пространственная сложность будет O(sum(tickets)) - сумма всех элементов массива, т.к. каждое уменьшение элемента массива требует прохода через очередь.
К тому же код достаточно длинный.
Есть решение элегантнее:)
Итак, алгоритм:
Основная идея — подсчитать, сколько билетов получит каждый человек, пока человек под индексом k не получит все свои билеты. Для этого нужно учитывать два сценария:
1. Если человек находится перед человеком с индексом k, он может получить только столько билетов, сколько у него изначально было, или столько же, сколько у человека под индексом k, если у него больше билетов.
2. Если человек находится после человека с индексом k, он может получить максимум на один билет меньше, чем человек под индексом k.
Итак, код:
public int timeRequiredToBuy(int[] tickets, int k) {
int seconds = 0;
for (int i = 0; i < tickets.length; i++) {
if (i <= k) {
seconds += Math.min(tickets[i], tickets[k]);
} else {
seconds += Math.min(tickets[i], tickets[k] - 1);
}
}
return seconds;
}Временная сложность - O(n), так как мы проходим по массиву tickets один раз.
Пространственная сложность - O(1), так как требуется постоянное кол-во памяти под переменную seconds.
Спасибо за ваши реакции на посты, приятно!🙌