เรียงช่วงตามจุดเริ่มต้น

ช่วงคือคู่ของตัวเลข ซึ่งประกอบด้วยจุดเริ่มต้นและจุดสิ้นสุด เช่น [2, 5] โจทย์เกี่ยวกับช่วงส่วนใหญ่จะให้รายการของคู่เหล่านี้ 📏

ช่วงดิบอาจมาในลำดับใดก็ได้ ทำให้วิเคราะห์ได้ยาก การ จัดเรียงช่วงเหล่านี้ก่อนจะเปลี่ยนความยุ่งเหยิงให้เป็นการกวาดผ่านจากซ้ายไปขวาที่เป็นระเบียบ

การดำเนินการมาตรฐานคือ sort ตามค่า จุดเริ่มต้น ตอนนี้แต่ละช่วงจะเริ่มต้นที่ตำแหน่งเดียวกับหรือหลังช่วงก่อนหน้า คุณจึงสแกนไปข้างหน้าได้เพียงครั้งเดียว

หากเก็บช่วงในรูปทูเพิล Python จะจัดเรียงตามสมาชิก ตัวแรก แล้วจึงตามสมาชิกตัวที่สองให้โดยอัตโนมัติ จึงไม่จำเป็นต้องใช้ฟังก์ชันคีย์ในกรณีนี้

การจัดเรียงตามจุดเริ่มต้นทำให้คุณประมวลผลเหตุการณ์ตามลำดับ เวลา ช่วงถัดไปจะเริ่มทีหลังได้เท่านั้น ซึ่งเป็นค่าคงที่สำคัญสำหรับการกวาดผ่าน

เมื่อช่วงสองช่วงมีจุดเริ่มต้นเดียวกัน คีย์ ลำดับรองจะเป็นตัวตัดสินลำดับ การจัดเรียงตาม (start, end) จะทำให้ช่วงที่สั้นกว่าอยู่ก่อน ซึ่งมักมีประโยชน์

โจทย์บางข้อ เช่น การจัดตารางเหตุการณ์ให้ได้มากที่สุด จะให้ sort ตาม จุดสิ้นสุดแทน เลือกคีย์ให้ตรงกับข้อมูลที่การกวาดผ่านของคุณต้องใช้

การจัดเรียงใช้เวลา O(n log n) ซึ่งถือว่าประหยัดและมักเป็นส่วนที่ใช้เวลามากที่สุดของโจทย์เหล่านี้ ส่วนการกวาดผ่านที่ตามมาใช้เวลาเพียง O(n)

หากแต่ละช่วงมีรหัสหรือน้ำหนักกำกับอยู่ ให้ sort ทั้ง ระเบียน ไม่ใช่เฉพาะขอบเขต คีย์จะควบคุมลำดับ ขณะที่ข้อมูลจะถูกเก็บไปพร้อมกัน

อัลกอริทึมเกี่ยวกับช่วงเกือบทั้งหมดใช้รูปแบบ sort ก่อน แล้วกวาดผ่าน เมื่อจัดลำดับถูกต้อง การรวม การนับ และการจัดตารางจะกลายเป็นลูปง่าย ๆ

ลองนึกภาพว่าช่วงต่าง ๆ เป็นแขกที่กำลังมาถึงงานเลี้ยง การจัดเรียงตามจุดเริ่มต้นจะจัดพวกเขาเป็นแถวตามเวลา มาถึง ทำให้คุณทักทายได้ทีละคน

คุณกำลังจะรวมรายการช่วงเข้าด้วยกัน

ช่วงคือคู่ของจุดเริ่มต้นและจุดสิ้นสุด และการจัดเรียงตาม จุดเริ่มต้นจะเปลี่ยนรายการที่ยุ่งเหยิงให้เป็นการกวาดผ่านที่เป็นระเบียบ จัดเรียงก่อน แล้วประมวลผลไปข้างหน้าด้วยเวลา O(n) 🚀