โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

จำลองคิวธนาคาร

จำลองลูกค้าที่รอในแถวเดียวสำหรับพนักงานธนาคารหลายคน แล้วรายงานเวลารอ

สิ่งที่คุณจะได้เรียนรู้

  • ให้บริการลูกค้าแบบมาก่อนได้ก่อน
  • ติดตามว่าผู้ให้บริการแต่ละคนจะว่างเมื่อใด
  • รวบรวมสถิติสรุปจากการจำลอง

โจทย์

ธนาคารแห่งหนึ่งมีพนักงานเคาน์เตอร์ 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 ≤ จำนวนลูกค้า ≤ 2,000

0 ≤ เวลามาถึง ≤ 100,000

1 ≤ เวลารับบริการ ≤ 1,000

1 ≤ tellers ≤ 20

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก