On this page

ข้อ 72 · LC435 Non-overlapping Intervals (ช่วงที่ไม่ทับกัน) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

หาจำนวน interval ที่ต้องลบน้อยที่สุดให้ interval ที่เหลือไม่ overlap ด้วย greedy เก็บ interval ที่จบเร็วก่อน

โจทย์ (LC435): กำหนด array ของ interval ชื่อ intervals โดย intervals[i] = [start_i, end_i] ให้ return จำนวน interval น้อยที่สุดที่ต้องลบออก เพื่อให้ interval ที่เหลือไม่ overlap (ทับซ้อน) กันเลย โดย interval ที่ต่อกันปลายชนปลายพอดี ไม่ถือว่า overlap กัน

Example 1

Input:: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output:: 1
Explanation:: ลบ [1,3] ออกช่วงเดียว ที่เหลือ [1,2],[2,3],[3,4] ก็ไม่ทับกันแล้ว

Example 2

Input:: intervals = [[1,2],[1,2],[1,2]]
Output:: 2
Explanation:: ต้องลบ [1,2] ออกสองช่วง เหลือไว้ช่วงเดียวจึงจะไม่ทับกัน

Example 3

Input:: intervals = [[1,2],[2,3]]
Output:: 0
Explanation:: ไม่ต้องลบเลย เพราะทั้งสองช่วงต่อกันปลายชนปลายพอดี ไม่ถือว่า overlap

Constraints (ข้อจำกัด)

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 × 10^4 <= start_i < end_i <= 5 × 10^4

แนวทาง — ต้องใช้อะไร & คิดยังไง

ข้อนี้ใช้ sort + greedy แทนที่จะคิดว่าลบตัวไหน ให้พลิกมาคิดว่าเก็บ interval ให้ได้มากที่สุดโดยไม่ overlap แล้วคำตอบคือจำนวน interval ทั้งหมดลบด้วยจำนวนที่เก็บได้ นี่คือปัญหา activity selection คลาสสิก

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

sort intervals ตาม end (x[1])
initialize kept = 0 และ prev_end = ลบอนันต์ (-inf)
iterate แต่ละ interval ถ้า start >= prev_end แปลว่าไม่ overlap กับ interval ที่เก็บล่าสุด เก็บได้ (kept += 1, update prev_end = end)
ถ้าทับก็ข้าม interval นั้น (เท่ากับลบทิ้ง)
return len(intervals) - kept

จุดพลาดที่พบบ่อย

เงื่อนไขต้องใช้ start >= prev_end เพราะปลายชนกันไม่ถือว่าทับ ถ้าใช้ > จะลบเกินจำเป็น และอย่าเผลอ sort ตาม start เพราะ interval ยาวที่เริ่มก่อนอาจกินพื้นที่ interval สั้นหลายอันทำให้ greedy เลือกผิด

ไล่ทีละสเต็ป

จำลอง intervals = [[1,2],[2,3],[3,4],[1,3]] หลัง sort ตาม end ได้ [[1,2],[1,3],[2,3],[3,4]]

ช่วง	start	prev_end	start >= prev_end	การกระทำ	kept
[1,2]	1	-inf	จริง	เก็บ, prev_end=2	1
[1,3]	1	2	เท็จ	ข้าม (ลบ)	1
[2,3]	2	2	จริง	เก็บ, prev_end=3	2
[3,4]	3	3	จริง	เก็บ, prev_end=4	3

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def erase_overlap_intervals(intervals):
    # sort ตามจุดจบ เพื่อ greedy เก็บช่วงที่จบเร็วที่สุดก่อน
    intervals.sort(key=lambda x: x[1])

    kept = 0                    # จำนวนช่วงที่เก็บไว้ได้โดยไม่ทับ
    prev_end = float("-inf")    # จุดจบของช่วงที่เก็บล่าสุด
    for start, end in intervals:
        if start >= prev_end:
            # เริ่มหลัง (หรือชนพอดี) ช่วงก่อนหน้า เก็บได้
            kept += 1
            prev_end = end
        # ถ้าทับ ก็ข้ามช่วงนี้ (เท่ากับลบทิ้ง)
    return len(intervals) - kept

print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2
print(erase_overlap_intervals([[1,2],[2,3]]))              # 0

Output

1
2
0

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

เงื่อนไข start >= prev_end ใช้ >= เพราะโจทย์นี้ปลายชนกันไม่ถือว่าทับ ถ้าลืมและใช้ > จะลบเกินจำเป็น จุดพลาดอีกอย่างคือเผลอ sort ตาม start ซึ่งจะทำให้ greedy เลือกผิดในบางเคส (interval ยาวที่เริ่มก่อนอาจกินพื้นที่ interval สั้นหลายอัน)

Time O(n log n) หลัก ๆ มาจากการ sort ส่วนการ iterate เก็บเป็น O(n) · Space O(1) ถ้าไม่นับพื้นที่ที่ sort ใช้ ใช้ตัวแปรนับไม่กี่ตัว

💡 สรุป pattern

โจทย์ activity selection (เลือก interval ให้มากสุดโดยไม่ทับ) ให้ sort ตาม end แล้ว greedy เก็บ interval ที่จบเร็วก่อนเสมอ — สูตรนี้ใช้ได้ทั้งข้อเลือกมากสุดและข้อลบน้อยสุด