จำนวนลูกศรน้อยที่สุดเพื่อทำลายลูกโป่ง (Minimum Number of Arrows to Burst Balloons) ใน C++

จำนวนลูกศรน้อยที่สุดเพื่อทำลายลูกโป่ง (Minimum Number of Arrows to Burst Balloons)

มีลูกโป่งทรงกลมกระจายอยู่ในพื้นที่ 2 มิติ แต่ละลูกมีพิกัดเริ่มต้นและสิ้นสุดของเส้นผ่านศูนย์กลางแนวนอน (start < end) ยิงลูกศรขึ้นไปตามแนวตั้งที่ตำแหน่ง x จะทำลายลูกโป่งที่ xstart ≤ x ≤ xend หาจำนวนลูกศรน้อยที่สุดเพื่อทำลายลูกโป่งทั้งหมด

ตัวอย่าง: [[10,16],[2,8],[1,6],[7,12]] → 2 (ยิงที่ 6 ทำลาย [2,8] และ [1,6], ยิงที่ 11 ทำลายอีกสองลูก)

ขั้นตอนการแก้ปัญหา (Greedy + Sort by End)

1. เรียงลูกโป่งตามตำแหน่งสิ้นสุด (end) จากน้อยไปมาก
2. currEnd = points[0][1], cnt = 1
3. วนลูป i = 1 ถึง n-1:
   • ถ้า currEnd < points[i][0] (ไม่ทับซ้อน): cnt++, currEnd = points[i][1]
4. คืนค่า cnt

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        sort(points.begin(), points.end(), [](auto& a, auto& b) {
            return a[1] < b[1];
        });
        int cnt = 1, currEnd = points[0][1];
        for (int i = 1; i < points.size(); i++) {
            if (currEnd < points[i][0]) {
                cnt++;
                currEnd = points[i][1];
            }
        }
        return cnt;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [[10,16],[2,8],[1,6],[7,12]]

Output: 2