ข้อ 73 · LC452 Minimum Number of Arrows to Burst Balloons (ลูกศรเจาะลูกโป่ง) 🟡

โจทย์ (LC452): มีลูกโป่งทรงกลมติดอยู่บนกำแพงซึ่งแทนด้วยระนาบ XY แต่ละลูกแทนด้วย array 2 มิติชื่อ points โดย points[i] = [x_start, x_end] คือเส้นผ่านศูนย์กลางแนวนอนของลูกโป่งลูกที่ i ยิงลูกศรขึ้นตรง ๆ ในแนวแกน y จากตำแหน่ง x ใด ๆ ได้ไม่จำกัดจำนวน ลูกศรที่ยิงจากตำแหน่ง x จะเจาะทะลุลูกโป่งทุกลูกที่ x_start <= x <= x_end ไปเรื่อย ๆ ไม่มีที่สิ้นสุด ให้ return จำนวนลูกศรน้อยที่สุดที่ทำให้ลูกโป่งทุกลูกแตก

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

ข้อนี้ใช้ sort + greedy คล้ายข้อก่อน ต่างที่คราวนี้เรามองว่าลูกศรหนึ่งดอกเจาะได้ทุกลูกที่ครอบตำแหน่งเดียวกัน จึงอยากยิงให้แต่ละดอกครอบลูกโป่งได้มากที่สุด

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

1. ถ้า points ว่างให้ return 0
2. sort points ตาม end (x[1])
3. ยิงลูกแรก arrows = 1 ที่ arrow_x = end ของลูกโป่งลูกแรก
4. iterate ลูกที่เหลือ ถ้า start > arrow_x แปลว่าลูกนี้เริ่มหลังลูกศร ต้องยิงใหม่ (arrows += 1, arrow_x = end)
5. ถ้า start <= arrow_x ลูกนี้แตกด้วยลูกศรเดิม ไม่ต้องทำอะไร สุดท้าย return arrows

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

จำลอง points = [[10,16],[2,8],[1,6],[7,12]] หลัง sort ตาม end ได้ [[1,6],[2,8],[7,12],[10,16]]

def find_min_arrows(points):
    if not points:
        return 0
    # sort ตามจุดจบ แล้วยิงลูกศรที่ปลายของลูกแรกในแต่ละกลุ่ม
    points.sort(key=lambda x: x[1])

    arrows = 1
    arrow_x = points[0][1]   # ยิงลูกแรกที่จุดจบของลูกโป่งลูกแรก
    for start, end in points[1:]:
        if start > arrow_x:
            # ลูกนี้เริ่มหลังลูกศรที่ยิงไป ต้องยิงลูกใหม่
            arrows += 1
            arrow_x = end
        # ถ้า start <= arrow_x ลูกนี้ก็แตกด้วยลูกศรเดิม
    return arrows

print(find_min_arrows([[10,16],[2,8],[1,6],[7,12]]))  # 2
print(find_min_arrows([[1,2],[3,4],[5,6],[7,8]]))     # 4
print(find_min_arrows([[1,2],[2,3],[3,4],[4,5]]))     # 2

2
4
2