418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 4

เพื่อให้สัญลักษณ์ดูง่าย เราให้ $a(i)=b(i)+r(i)\,$ สำหรับ $1\leq i\leq n\,$ ทุกตัว

อัลกอริทึม

เรียงผู้เข้าแข่งขันตาม $a(i)\,$ จากน้อยไปหามาก แล้วจัดลำดับการเริ่มต้นแข่งตามนั้น

เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้สามารถทำงานได้ในเวลา $O(n\log n)\,$

ข้อสังเกต

ก่อนที่เราจะไปพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้อง เราจะตั้งข้อสังเกตดังต่อไปนี้

ให้ $f(i)\,$ แทนเวลาที่ผู้เข้าแข่งขันหมายเลข $i\,$ วายน้ำเสร็จ แล้วเราจะได้ว่าเวลาที่ผู้เข้าแข่งขันคนที่ช้าที่สุดจบการแข่งขันคือเวลา $\max _{1\leq i\leq n}\{f(i)+a(i)\}\,$

ดังนั้นอัลกอริทึมข้างบนจึงเป็นอัลกอริทึมทีทำให้ $\max _{1\leq i\leq n}\{f(i)+a(i)\}\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

การพิสูจน์ความถูกต้องของอัลกอริทึม

เราจะพิสูจน์ว่าอัลกอริทึมทำงานได้ถูกต้องโดยใช้ exchange argument

ให้ $\mathrm {OPT} \,$ แทนวิธีการจัดลำดับการเริ่มแข่งขันที่ดีที่สุด (กล่าวคือผู้เข้าแข่งขันที่จบการแข่งขันช้าที่สุดนั้นจบการแข่งขันเร็วที่สุดเท่าที่จะทำได้) เราจะแสดงว่าเราสามารถเปลี่ยน $\mathrm {OPT} \,$ ไปเป็นวิธีการจัดลำดับการแข่งขันที่ผู้เข้าแข่งขันถูกเรียงตามเวลา $a(i)\,$ โดยไม่ทำให้เวลาจบการแข่งขันของผู้เข้าแข่งขันที่จบเป็นคนสุดท้ายช้าลงได้ดังต่อไปนี้