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

Mô phỏng hàng đợi ở ngân hàng

Mô phỏng khách hàng xếp chung một hàng chờ nhiều giao dịch viên và báo cáo thời gian chờ.

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

  • Phục vụ khách theo thứ tự đến trước phục vụ trước
  • Theo dõi thời điểm mỗi quầy trở nên rảnh
  • Thu thập số liệu tổng hợp từ một mô phỏng

Đề bài

Xem bản gốc (English)

Một ngân hàng có tellers giao dịch viên và một hàng chờ duy nhất. Khách hàng i đến vào phút arrivals[i] và cần service[i] phút tại quầy. Khách được phục vụ đúng theo thứ tự đến (thứ tự trong danh sách). Khi lên đầu hàng, khách sẽ đến quầy của giao dịch viên rảnh sớm nhất (nếu nhiều người cùng rảnh thì chọn người có số thứ tự nhỏ nhất), và bắt đầu vào thời điểm muộn hơn giữa lúc khách đến và lúc giao dịch viên đó rảnh. Mọi giao dịch viên đều rảnh từ phút 0.

Thời gian chờ của một khách bằng thời điểm bắt đầu trừ thời điểm đến.

Hãy viết bank_queue_simulation(arrivals, service, tellers).

Đầu vào

arrivals: Các phút khách đến, theo thứ tự không giảm.

service: Số phút phục vụ của từng khách, theo cùng thứ tự.

tellers: Số giao dịch viên.

Đầu ra

Trả về [total_wait, longest_wait, last_finish]: tổng thời gian chờ, thời gian chờ lâu nhất của một khách, và phút mà khách cuối cùng xong việc. Nếu không có khách nào, trả về [0, 0, 0].

Ràng buộc

0 ≤ số khách ≤ 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

Khách 1 và 2 được phục vụ ngay (lúc 0 và lúc 1). Giao dịch viên 2 rảnh lúc 4 nên khách 3 chờ 2 phút; giao dịch viên 1 rảnh lúc 5 nên khách 4 chờ 2 phút. Thời điểm xong cuối cùng là 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

Với một giao dịch viên, thời gian chờ lần lượt là 0, 4 và 8, và khách cuối cùng xong lúc 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

Giữ một mảng lưu phút mà mỗi giao dịch viên trở nên rảnh.

Gợi ý 2

Với mỗi khách, chọn thời điểm rảnh nhỏ nhất (nếu bằng nhau thì chọn chỉ số nhỏ nhất).

Gợi ý 3

Thời điểm bắt đầu là giá trị muộn hơn giữa lúc đến và lúc rảnh đó; thời gian chờ bằng thời điểm bắt đầu trừ lúc đến.

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

thời gian O(n × k), bộ nhớ phụ O(k)

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.