LeetCode Merge Intervals: เรียงก่อนแล้วค่อยยุบช่วงซ้อน

โจทย์ให้รายการช่วง [เริ่ม, จบ] แล้วให้รวมช่วงที่ซ้อนหรือชนกัน เช่น [[1,3],[2,6],[8,10]] ได้ [[1,6],[8,10]]

แนวทางที่ 1: เทียบทุกคู่แล้วยุบซ้ำ

ลองหาคู่ที่ซ้อนแล้วรวม วนจนนิ่ง

• เข้าใจแนวคิดการซ้อน แต่ควบคุมรอบยาก เวลาแย่และบั๋งง่าย
• ใช้สอนนิยาม “ซ้อน” มากกว่าเป็นคำตอบจบ

แนวทางที่ 2: เรียงตามจุดเริ่ม แล้วสแกนครั้งเดียว (แนะนำหลัก)

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

นี่เป็นตัวอย่างโค้ดแบบ fragment / pseudocode สำหรับอธิบายแนวคิด:

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for start, end in intervals:
        if not out or start > out[-1][1]:
            out.append([start, end])
        else:
            out[-1][1] = max(out[-1][1], end)
    return out

• เวลา O(n log n) จากเรียง พื้นที่ O(n) สำหรับผลลัพธ์
• เป็นคำตอบมาตรฐานในสัมภาษณ์

แนวทางที่ 3: เรียงแล้วใช้สแต็ก

แนวเดียวกับข้อ 2 แต่เก็บผลใน stack ชัด ๆ ว่าช่วงบนสุดคือช่วงที่กำลังขยาย

• ความซับซ้อนเท่ากัน บางคนอธิบายภาพ stack ง่ายกว่า

แนวทางที่ 4: Line sweep

ใส่เหตุการณ์ +1 ที่จุดเริ่ม และ -1 ที่จุดจบ แล้วกวาดบนเส้นจำนวน

• ยืดหยุ่นเมื่อมีคำถามซ้อนหลายแบบ เช่น นับความหนาสูงสุด
• สำหรับ Merge Intervals ล้วน ๆ มักยาวเกินจำเป็นบนไวท์บอร์ด

แนวทางที่ 5: ข้อมูลพิเศษ

ถ้าช่วงถูกเรียงมาแล้ว ตัดค่าใช้จ่ายการเรียงเหลือสแกน O(n) ถ้ามาจากฐานข้อมูลที่จัด index อยู่แล้ว ให้ใช้ประโยชน์นั้นในโปรดักชัน

แผนภาพด้านล่างเป็น fragment / pseudocode ของลำดับยุบช่วง:

flowchart LR
  A[เรียงตามจุดเริ่ม] --> B[อ่านช่วงถัดไป]
  B --> C{ซ้อนกับช่วงล่าสุด?}
  C -->|ใช่| D[ขยายจุดจบ]
  C -->|ไม่| E[เพิ่มช่วงใหม่]
  D --> B
  E --> B

เลือกใช้เมื่อไหร่

สถานการณ์	แนะนำ
มือใหม่	วาดช่วงบนเส้นจำนวนแล้วเรียงก่อนยุบ
ไวท์บอร์ด	เรียง + สแกนหนึ่งรอบ
โปรดักชันมีช่วงจำนวนมากและถูกเรียงแล้ว	สแกนอย่างเดียว หรือโครงสร้าง interval tree ถ้านอกโจทย์

Recap

• นิยามให้ชัดว่าชนขอบนับว่าซ้อนหรือไม่ตามโจทย์
• เรียงก่อนเสมอถ้าอินพุตไม่รับประกันลำดับ
• จดว่าคอขวดคือ O(n log n) จากเรียง
• เตรียมเคสช่วงย่อยอยู่ใในอีกช่วง และช่วงแตะขอบพอดีครับ