В банке работают tellers кассиров, а очередь одна. Клиент i приходит в минуту arrivals[i], и его обслуживание занимает service[i] минут. Клиентов обслуживают строго в порядке прихода (в порядке списков). Когда клиент оказывается первым в очереди, он идёт к кассиру, который освободится раньше всех (при равенстве - к кассиру с меньшим номером), и начинает обслуживаться в более поздний из двух моментов: время своего прихода или время, когда кассир освободится. Все кассиры свободны с минуты 0.
Ожидание клиента - это время начала обслуживания минус время прихода.
Реализуйте bank_queue_simulation(arrivals, service, tellers).
Входные данные
arrivals: минуты прихода в неубывающем порядке.
service: время обслуживания каждого клиента в минутах, в том же порядке.
tellers: количество кассиров.
Выходные данные
Верните [total_wait, longest_wait, last_finish]: сумму всех ожиданий, самое долгое ожидание и минуту, когда закончится обслуживание последнего клиента. Если клиентов нет, верните [0, 0, 0].
Ограничения
0 ≤ количество клиентов ≤ 2000
0 ≤ arrival ≤ 100 000
1 ≤ service ≤ 1000
1 ≤ tellers ≤ 20
Примеры
Ввод:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2
Ожидаемый вывод:
expected = [4, 2, 8]
Ввод:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;
Ожидаемый вывод:
std::vector<long long> expected = {4, 2, 8};
Ввод:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;
Ожидаемый вывод:
long[] expected = new long[] {4, 2, 8};
Пояснение
Клиенты 1 и 2 начинают сразу (в 0 и в 1). Кассир 2 освобождается в 4, поэтому клиент 3 ждёт 2; кассир 1 освобождается в 5, поэтому клиент 4 ждёт 2. Последний клиент заканчивает в max(8, 7) = 8: [4, 2, 8].
Ввод:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1
Ожидаемый вывод:
expected = [12, 8, 12]
Ввод:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;
Ожидаемый вывод:
std::vector<long long> expected = {12, 8, 12};
Ввод:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;
Ожидаемый вывод:
long[] expected = new long[] {12, 8, 12};
Пояснение
При одном кассире ожидания равны 0, 4 и 8, а последний клиент заканчивает в 12: [12, 8, 12].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Храните массив с минутой, когда освобождается каждый кассир.
Подсказка 2
Для каждого клиента выбирайте наименьшее время освобождения (при равенстве - наименьший индекс).
Подсказка 3
Начало обслуживания - более позднее из времени прихода и этого времени освобождения; ожидание - начало минус приход.
Ожидаемая сложность
время O(n × k), доп. память O(k)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.