All challenges
Medium 0 solved 0% acceptance

Bank Queue Simulation

Simulate customers waiting in one line for several bank tellers and report the waiting times.

What you'll learn

  • Serve customers in first-come, first-served order
  • Track when each server becomes free
  • Collect summary statistics from a simulation

Problem

A bank has tellers tellers and a single waiting line. Customer i arrives at minute arrivals[i] and needs service[i] minutes at a teller. Customers are served strictly in arrival order (the order of the lists). When a customer reaches the front of the line, they go to the teller who becomes free the earliest (the lowest numbered one on a tie), and start at the later of their arrival time and that teller's free time. A teller is free from minute 0.

A customer's wait is their start time minus their arrival time.

Implement bank_queue_simulation(arrivals, service, tellers).

Input

arrivals: Arrival minutes in non-decreasing order.

service: Service minutes for each customer, in the same order.

tellers: The number of tellers.

Output

Return [total_wait, longest_wait, last_finish]: the sum of all waits, the largest single wait, and the minute the last customer finishes. With no customers return [0, 0, 0].

Constraints

0 ≤ number of customers ≤ 2,000

0 ≤ arrival ≤ 100,000

1 ≤ service ≤ 1,000

1 ≤ tellers ≤ 20

Examples

Example 1
Input:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

Expected output:
expected = [4, 2, 8]
Input:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;

Expected output:
std::vector<long long> expected = {4, 2, 8};
Input:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;

Expected output:
long[] expected = new long[] {4, 2, 8};

Explanation

Customers 1 and 2 start at once (0 and 1). Teller 2 frees at 4, so customer 3 waits 2; teller 1 frees at 5, so customer 4 waits 2. Last finish is max(8, 7) = 8: [4, 2, 8].

Example 2
Input:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

Expected output:
expected = [12, 8, 12]
Input:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;

Expected output:
std::vector<long long> expected = {12, 8, 12};
Input:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;

Expected output:
long[] expected = new long[] {12, 8, 12};

Explanation

With one teller the waits are 0, 4 and 8, and the last customer finishes at 12: [12, 8, 12].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Keep an array with the minute each teller becomes free.

Hint 2

For each customer pick the smallest free time (lowest index on a tie).

Hint 3

Start time is the later of arrival and that free time; the wait is start minus arrival.

Expected complexity

O(n × k) time, O(k) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.