ผสานช่วงที่ทับซ้อนกัน
รวมช่วงที่แตะกันหรือทับซ้อนกัน
ผสานช่วงที่ทับซ้อนกัน เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เป้าหมายของการรวมช่วง
เมื่อได้รับช่วงจำนวนมาก คุณต้องการ รวมช่วงที่แตะกันหรือซ้อนทับกันให้เหลือช่วงที่ไม่ซ้อนทับกันจำนวนน้อยที่สุด 🧩
เมื่อช่วงสองช่วงซ้อนทับกัน
ช่วงสองช่วงซ้อนทับกันเมื่อช่วงหนึ่งเริ่มต้นก่อนที่อีกช่วงจะ สิ้นสุด หลังจากจัดเรียงตามจุดเริ่มต้นแล้ว หมายความว่าจุดเริ่มต้นถัดไปต้องน้อยกว่าหรือเท่ากับจุดสิ้นสุดปัจจุบัน
จัดเรียงก่อนเสมอ
การรวมช่วงจะทำงานจากซ้ายไปขวาได้ก็ต่อเมื่อช่วงต่าง ๆ อยู่ในลำดับที่ถูกต้อง ดังนั้นให้เริ่มด้วยการ จัดเรียงตามจุดเริ่มต้น นี่คือพื้นฐานของการกวาดผ่านทั้งหมด
intervals.sort(key=lambda x: x[0])เก็บช่วงปัจจุบันไว้
เดินผ่านรายการที่จัดเรียงแล้ว โดยเก็บช่วงที่รวมอยู่ ปัจจุบันไว้หนึ่งช่วง ช่วงใหม่แต่ละช่วงจะขยายช่วงเดิมหรือเริ่มช่วงใหม่
ขยายเมื่อซ้อนทับกัน
หากจุดเริ่มต้นถัดไปอยู่ภายในช่วงปัจจุบัน แสดงว่าช่วงทั้งสองซ้อนทับกัน ดังนั้นให้ ขยายจุดสิ้นสุดปัจจุบันเป็นค่าที่มากกว่าระหว่างจุดสิ้นสุดทั้งสอง
cur_end = max(cur_end, end)เลือกจุดสิ้นสุดที่มากที่สุด
ใช้ max เป็นจุดสิ้นสุดใหม่เสมอ ช่วงสั้นที่อยู่ภายในช่วงยาวต้องไม่ทำให้ช่วงที่สร้างไว้แล้วสั้นลง
ปิดช่วงแล้วเปิดช่วงใหม่
หากจุดเริ่มต้นถัดไปอยู่เลยจุดสิ้นสุดปัจจุบัน แสดงว่ามี ช่องว่าง ให้เพิ่มช่วงที่เสร็จแล้วลงในคำตอบ และเริ่มช่วงปัจจุบันช่วงใหม่
result.append([cur_start, cur_end])อย่าลืมช่วงสุดท้าย
ลูปจะสร้างช่วงสุดท้ายขึ้นมาแต่ไม่ได้นำไปเก็บ หลังจบลูป ให้ append ช่วงปัจจุบันสุดท้ายลงไปเพื่อไม่ให้ช่วงนั้นสูญหาย
การแตะกันถือว่าทับซ้อน
โปรดตัดสินใจว่า [1, 3] และ [3, 5] ควรถูกรวมกันหรือไม่ โดยทั่วไปควรรวม ดังนั้นให้ใช้ start <= cur_end โปรดอ่านโจทย์เพื่อยืนยันกฎสำหรับกรณีขอบนี้
การกวาดทั้งหมด
การวนผ่านหนึ่งรอบหลังการเรียงลำดับจะให้ช่วงที่รวมแล้วทั้งหมด ดังนั้นวิธีนี้ใช้เวลาโดยรวม O(n log n) จาก sort ร่วมกับการกวาดแบบเชิงเส้น
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eการใช้งานที่พบบ่อย
การรวมช่วงช่วยเสริมประสิทธิภาพปฏิทินและระบบจอง: รวมบล็อกเวลาที่ไม่ว่างเพื่อดู เวลาว่างที่มีอยู่จริง โจทย์การแข่งขันหลายข้อซ่อนรูปแบบเดียวกันนี้ไว้
ตรวจสอบอย่างรวดเร็ว
คุณรวมช่วงหลังจากเรียงลำดับตามจุดเริ่มต้น
สรุป
เรียงลำดับตามจุดเริ่มต้น เก็บช่วงปัจจุบันไว้ แล้ว ขยาย ด้วยค่ามากที่สุดเมื่อทับซ้อนกัน หรือเพิ่มช่วงแล้วเริ่มใหม่เมื่อพบช่องว่าง อย่าลืมใช้ append ครั้งสุดท้ายด้วย 🚀
คำถามที่พบบ่อย
บทเรียน “ผสานช่วงที่ทับซ้อนกัน” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ผสานช่วงที่ทับซ้อนกัน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ผสานช่วงที่ทับซ้อนกัน”
รวมช่วงที่แตะกันหรือทับซ้อนกัน คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “ผสานช่วงที่ทับซ้อนกัน” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- เรียงช่วงตามจุดเริ่มต้น
- ผสานช่วงที่ทับซ้อนกัน
- กวาดเส้นเพื่อหาการทับซ้อนสูงสุด
- การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน