Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Bank Queue Simulation

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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].

Ràng buộc

0 ≤ number of customers ≤ 2,000

0 ≤ arrival ≤ 100,000

1 ≤ service ≤ 1,000

1 ≤ tellers ≤ 20

Ví dụ

Ví dụ 1
Đầu vào:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2

Kết quả mong đợi:
expected = [4, 2, 8]
Đầu vào:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;

Kết quả mong đợi:
std::vector<long long> expected = {4, 2, 8};
Đầu vào:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;

Kết quả mong đợi:
long[] expected = new long[] {4, 2, 8};

Giải thích

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].

Ví dụ 2
Đầu vào:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1

Kết quả mong đợi:
expected = [12, 8, 12]
Đầu vào:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;

Kết quả mong đợi:
std::vector<long long> expected = {12, 8, 12};
Đầu vào:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;

Kết quả mong đợi:
long[] expected = new long[] {12, 8, 12};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Keep an array with the minute each teller becomes free.

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.