Intervals — พื้นฐาน & แนวคิด

Intervals (ช่วง) คือกลุ่มโจทย์ที่ข้อมูลแต่ละชิ้นเป็น interval (ช่วง) มี start (จุดเริ่ม) กับ end (จุดจบ) เช่น [1,3] หมายถึงช่วงตั้งแต่ 1 ถึง 3 โจทย์มักถามเรื่อง overlap (การทับซ้อน) ของ interval เช่น ต้องลบ interval ไหนออกบ้างให้ไม่ทับกัน หรือ merge (รวม) interval ที่ซ้อนกันเข้าด้วยกัน กุญแจสำคัญเกือบทุกข้อคือ sort ก่อน แล้วค่อย iterate (วน) เทียบทีละคู่

นิยามของคำว่า ทับกัน

สอง interval [a1, b1] กับ [a2, b2] จะ overlap เมื่อ interval หนึ่งเริ่มก่อนที่อีก interval จะจบ พูดง่าย ๆ คือถ้า sort ให้ interval แรกมาก่อน interval ที่สองจะทับก็ต่อเมื่อ start ของ interval ที่สองน้อยกว่า end ของ interval แรก เช่น [1,3] กับ [2,4] overlap กัน (เพราะ 2 < 3) แต่ [1,2] กับ [2,4] มักถือว่าไม่ทับ (แค่ปลายชนกันที่ 2 แต่ไม่ซ้อนกัน)

sort แล้ว greedy

เทคนิคหลักคือ sort interval ทั้งหมดก่อน จะ sort ตาม start หรือ end ขึ้นกับโจทย์ จากนั้น iterate ทีละ interval แบบ greedy คือตัดสินใจโดยดูแค่ interval ล่าสุดที่เก็บไว้เทียบกับ interval ปัจจุบัน ไม่ต้องมองย้อนกลับไปไกล

# โครงทั่วไปของโจทย์ intervals
intervals = [[1, 3], [2, 4], [3, 5]]

# sort ตามจุดจบ (บางโจทย์ sort ตามจุดเริ่ม)
intervals.sort(key=lambda x: x[1])

prev_end = float("-inf")   # จุดจบของช่วงล่าสุดที่เลือกไว้
for start, end in intervals:
    if start >= prev_end:
        # ไม่ทับกับช่วงก่อนหน้า เลือกช่วงนี้ได้
        prev_end = end
    else:
        # ทับกัน ต้องตัดสินใจ (ข้าม/ลบ ช่วงนี้ ฯลฯ)
        pass

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